Name: Rohit Goutam Maity

Assignment: HW4

Course Number: DSC 441

Problem 1 (15 points):

For this problem, you will tune and apply kNN and compare it to other classifiers. We will use the wine quality data, which has a number of measurements about chemical components in wine, plus a quality rating. There are separate files for red and white wines, so the first step is some data preparation.

Approach:

1.Data Loading and Preparation:

2.Data Splitting:

  1. kNN Tuning:
  1. Comparison with Other Classifiers:

a.Load the two provided wine quality datasets and prepare them by (1) ensuring that all the variables have the right type (e.g., what is numeric vs. factor), (2) adding a type column to each that indicates if it is red or white wine and (2) merging the two tables together into one table (hint: try full_join()). You now have one table that contains the data on red and white wine, with a column that tells if the wine was from the red or white set (the type column you made).

# Load necessary libraries
library(dplyr)

Attaching package: ‘dplyr’

The following objects are masked from ‘package:stats’:

    filter, lag

The following objects are masked from ‘package:base’:

    intersect, setdiff, setequal, union
# Load the datasets
red_wine <- read.csv("winequality-red.csv", sep = ";")
white_wine <- read.csv("winequality-white.csv", sep = ";")

# Check and adjust variable types if necessary
str(red_wine)
'data.frame':   1599 obs. of  12 variables:
 $ fixed.acidity       : num  7.4 7.8 7.8 11.2 7.4 7.4 7.9 7.3 7.8 7.5 ...
 $ volatile.acidity    : num  0.7 0.88 0.76 0.28 0.7 0.66 0.6 0.65 0.58 0.5 ...
 $ citric.acid         : num  0 0 0.04 0.56 0 0 0.06 0 0.02 0.36 ...
 $ residual.sugar      : num  1.9 2.6 2.3 1.9 1.9 1.8 1.6 1.2 2 6.1 ...
 $ chlorides           : num  0.076 0.098 0.092 0.075 0.076 0.075 0.069 0.065 0.073 0.071 ...
 $ free.sulfur.dioxide : num  11 25 15 17 11 13 15 15 9 17 ...
 $ total.sulfur.dioxide: num  34 67 54 60 34 40 59 21 18 102 ...
 $ density             : num  0.998 0.997 0.997 0.998 0.998 ...
 $ pH                  : num  3.51 3.2 3.26 3.16 3.51 3.51 3.3 3.39 3.36 3.35 ...
 $ sulphates           : num  0.56 0.68 0.65 0.58 0.56 0.56 0.46 0.47 0.57 0.8 ...
 $ alcohol             : num  9.4 9.8 9.8 9.8 9.4 9.4 9.4 10 9.5 10.5 ...
 $ quality             : int  5 5 5 6 5 5 5 7 7 5 ...
str(white_wine)
'data.frame':   4898 obs. of  12 variables:
 $ fixed.acidity       : num  7 6.3 8.1 7.2 7.2 8.1 6.2 7 6.3 8.1 ...
 $ volatile.acidity    : num  0.27 0.3 0.28 0.23 0.23 0.28 0.32 0.27 0.3 0.22 ...
 $ citric.acid         : num  0.36 0.34 0.4 0.32 0.32 0.4 0.16 0.36 0.34 0.43 ...
 $ residual.sugar      : num  20.7 1.6 6.9 8.5 8.5 6.9 7 20.7 1.6 1.5 ...
 $ chlorides           : num  0.045 0.049 0.05 0.058 0.058 0.05 0.045 0.045 0.049 0.044 ...
 $ free.sulfur.dioxide : num  45 14 30 47 47 30 30 45 14 28 ...
 $ total.sulfur.dioxide: num  170 132 97 186 186 97 136 170 132 129 ...
 $ density             : num  1.001 0.994 0.995 0.996 0.996 ...
 $ pH                  : num  3 3.3 3.26 3.19 3.19 3.26 3.18 3 3.3 3.22 ...
 $ sulphates           : num  0.45 0.49 0.44 0.4 0.4 0.44 0.47 0.45 0.49 0.45 ...
 $ alcohol             : num  8.8 9.5 10.1 9.9 9.9 10.1 9.6 8.8 9.5 11 ...
 $ quality             : int  6 6 6 6 6 6 6 6 6 6 ...
# Convert variables if needed, e.g., as.factor() for categorical variables

# Add a type column to each dataset
red_wine$type <- "red"
white_wine$type <- "white"

# Combine the datasets
wine_data <- full_join(red_wine, white_wine)
Joining with `by = join_by(fixed.acidity, volatile.acidity, citric.acid, residual.sugar, chlorides, free.sulfur.dioxide, total.sulfur.dioxide, density, pH, sulphates, alcohol, quality, type)`
# View the combined dataset structure to ensure correctness
str(wine_data)
'data.frame':   6497 obs. of  13 variables:
 $ fixed.acidity       : num  7.4 7.8 7.8 11.2 7.4 7.4 7.9 7.3 7.8 7.5 ...
 $ volatile.acidity    : num  0.7 0.88 0.76 0.28 0.7 0.66 0.6 0.65 0.58 0.5 ...
 $ citric.acid         : num  0 0 0.04 0.56 0 0 0.06 0 0.02 0.36 ...
 $ residual.sugar      : num  1.9 2.6 2.3 1.9 1.9 1.8 1.6 1.2 2 6.1 ...
 $ chlorides           : num  0.076 0.098 0.092 0.075 0.076 0.075 0.069 0.065 0.073 0.071 ...
 $ free.sulfur.dioxide : num  11 25 15 17 11 13 15 15 9 17 ...
 $ total.sulfur.dioxide: num  34 67 54 60 34 40 59 21 18 102 ...
 $ density             : num  0.998 0.997 0.997 0.998 0.998 ...
 $ pH                  : num  3.51 3.2 3.26 3.16 3.51 3.51 3.3 3.39 3.36 3.35 ...
 $ sulphates           : num  0.56 0.68 0.65 0.58 0.56 0.56 0.46 0.47 0.57 0.8 ...
 $ alcohol             : num  9.4 9.8 9.8 9.8 9.4 9.4 9.4 10 9.5 10.5 ...
 $ quality             : int  5 5 5 6 5 5 5 7 7 5 ...
 $ type                : chr  "red" "red" "red" "red" ...

b. Use PCA to create a projection of the data to 2D and show a scatterplot with color showing the wine type.

# Load necessary libraries
library(ggplot2)
library(dplyr)

# Prepare data by excluding the 'type' column
wine_data_numeric <- wine_data %>%
  select(-type)

# Standardize the data
wine_data_scaled <- scale(wine_data_numeric)

# Perform PCA
pca_result <- prcomp(wine_data_scaled, center = TRUE, scale. = TRUE)

# Create a data frame with the first two principal components and wine type
pca_data <- data.frame(PC1 = pca_result$x[, 1],
                       PC2 = pca_result$x[, 2],
                       type = wine_data$type)

# Plot the PCA result
ggplot(pca_data, aes(x = PC1, y = PC2, color = type)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA of Wine Data", x = "Principal Component 1", y = "Principal Component 2") +
  theme_minimal()

c. We are going to try kNN, SVM and decision trees on this data. Based on the ‘shape’ of the data in the visualization from (b), which do you think will do best and why?

  1. k-Nearest Neighbors (kNN):
  • kNN can perform well with this dataset as the two types of wines (red and white) form fairly distinct clusters with some overlap.
  • However, the overlapping regions between red and white wines may reduce kNN’s accuracy since kNN classifies based on the majority of nearby points, which might lead to misclassifications in the overlapping area.
  1. Support Vector Machine (SVM):
  • SVM, especially with a non-linear kernel (e.g., radial basis function or polynomial), might perform well due to its ability to find a decision boundary that maximizes the margin between classes.
  • SVM could potentially separate the clusters effectively, even with some overlap, by focusing on maximizing the separation margin.
  1. Decision Trees:
  • Decision Trees might struggle slightly with the overlapping regions since they create axis-aligned splits. This could lead to a more complex tree with splits that attempt to separate the overlapping areas, potentially leading to overfitting.
  • If the data were clearly separable along certain feature axes, Decision Trees would perform better, but with the observed overlap, it may be more challenging for them to achieve optimal results.

Prediction: Given the overlap and the need for a smooth decision boundary, SVM is likely to perform best, as it can create a flexible boundary that better separates the two classes. kNN might perform well but could be affected by the overlap. Decision Trees may be less effective due to the complex decision boundary required.

d. Use kNN (tune k), use decision trees (basic rpart method is fine), and SVM (tune C) to predict type from the rest of the variables. Compare the accuracy values – is this what you expected? Can you explain it?

# Load necessary libraries
library(caret)
Loading required package: lattice
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     
library(rpart)
library(e1071)

# Ensure 'type' is a factor
wine_data$type <- as.factor(wine_data$type)

# Split the data into training and testing sets
set.seed(123)
train_index <- createDataPartition(wine_data$type, p = 0.7, list = FALSE)
train_data <- wine_data[train_index, ]
test_data <- wine_data[-train_index, ]

# 1. kNN with tuning
control <- trainControl(method = "cv", number = 10)
knn_model <- train(type ~ ., data = train_data, method = "knn", tuneLength = 10, trControl = control)
knn_predictions <- predict(knn_model, test_data)
knn_accuracy <- mean(knn_predictions == test_data$type)

# 2. Decision Tree (rpart)
tree_model <- rpart(type ~ ., data = train_data)
tree_predictions <- predict(tree_model, test_data, type = "class")
tree_accuracy <- mean(tree_predictions == test_data$type)

# 3. SVM with tuning for C
svm_model <- train(type ~ ., data = train_data, method = "svmLinear", tuneGrid = expand.grid(C = seq(0.1, 2, by = 0.1)), trControl = control)
svm_predictions <- predict(svm_model, test_data)
svm_accuracy <- mean(svm_predictions == test_data$type)

# Output accuracies for comparison
cat("kNN Accuracy:", knn_accuracy, "\n")
kNN Accuracy: 0.9332649 
cat("Decision Tree Accuracy:", tree_accuracy, "\n")
Decision Tree Accuracy: 0.9784394 
cat("SVM Accuracy:", svm_accuracy, "\n")
SVM Accuracy: 0.9958932 

Answers: Model Performance Comparison

After applying kNN, Decision Trees, and SVM on the wine quality dataset, we obtained the following accuracy results:

  • kNN Accuracy: 93.33%
  • Decision Tree Accuracy: 97.84%
  • SVM Accuracy: 99.59%

Interpretation of Results

  1. SVM:
  • With an accuracy of 99.59%, SVM performed the best among the three models, as initially expected. This high performance aligns well with our assumption that SVM’s flexible decision boundary is well-suited to handle the overlapping clusters in the data.
  • The tuning of the C parameter allowed SVM to maximize the margin while reducing misclassification, even in the areas where red and white wine classes overlap.
  1. Decision Tree:
  • Surprisingly, Decision Trees also achieved high accuracy (97.84%), outperforming kNN and coming close to SVM. This result suggests that the decision boundaries, though axis-aligned, were effective in capturing the differences between red and white wine in this dataset.
  • Despite initial expectations, Decision Trees were able to generalize well here, possibly because the features in this dataset provide clear enough separation for simple splits to be effective.
  1. kNN:
  • kNN performed well with an accuracy of 93.33%, but slightly lower than Decision Trees and SVM. This is consistent with our expectations, as kNN can be affected by overlapping regions between classes. In those areas, nearby points from both red and white wines can lead to some misclassifications.
  • The tuned k value helped in balancing bias and variance, but kNN was still limited by the data’s structure, especially in the overlapping regions.

Conclusion

These results align closely with our initial expectations, where SVM was predicted to perform best. However, the high accuracy of Decision Trees was unexpected and suggests that the features in this dataset allowed for relatively simple splits to achieve good separation. The performance differences highlight the importance of understanding the data distribution to select the most appropriate model.

e. Use the same already computed PCA again to show a scatter plot of the data and to visualize the labels for kNN, decision tree and SVM. Note that you do not need to recreate the PCA projection, you have already done this in 1b. Here, you just make a new visualization for each classifier using its labels for color (same points but change the color). Map the color results to the classifier, that is use the “predict” function to predict the class of your data, add it to your data frame and use it as a color. This is done for KNN in the tutorial, it should be similar for the others. Consider and explain the differences in how these classifiers performed.

# Use the existing PCA results
pca_data <- data.frame(PC1 = pca_result$x[, 1],
                       PC2 = pca_result$x[, 2],
                       true_type = wine_data$type)

# Generate predictions for each model
pca_data$knn_pred <- predict(knn_model, wine_data)
pca_data$tree_pred <- predict(tree_model, wine_data, type = "class")
pca_data$svm_pred <- predict(svm_model, wine_data)

# Load ggplot2 for plotting
library(ggplot2)

# Plot for kNN predictions
ggplot(pca_data, aes(x = PC1, y = PC2, color = knn_pred)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA of Wine Data with kNN Predictions", color = "kNN Prediction") +
  theme_minimal()


# Plot for Decision Tree predictions
ggplot(pca_data, aes(x = PC1, y = PC2, color = tree_pred)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA of Wine Data with Decision Tree Predictions", color = "Tree Prediction") +
  theme_minimal()


# Plot for SVM predictions
ggplot(pca_data, aes(x = PC1, y = PC2, color = svm_pred)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA of Wine Data with SVM Predictions", color = "SVM Prediction") +
  theme_minimal()

Answers:

kNN Predictions

  • Visualization: In the kNN plot, the boundary between red and white wines is well-defined, but there is a noticeable region of misclassifications in the overlapping area.
  • Performance: As expected, kNN performed well but struggled with points near the boundary between red and white wines. This is a typical limitation of kNN, as it relies on local neighbor majority voting, which can misclassify points in areas with close inter-class proximity.
  • Conclusion: kNN provides a reasonable separation but has difficulty with overlapping regions, leading to some incorrect classifications.

Decision Tree Predictions

  • Visualization: The Decision Tree plot shows a fairly clean separation between red and white wines, with fewer misclassifications compared to kNN in the overlapping regions.
  • Performance: The Decision Tree managed to create clear decision boundaries, effectively capturing the majority of red and white wine classes. However, there may be some rigidity in the boundary due to axis-aligned splits, which can lead to occasional errors near the decision threshold.
  • Conclusion: The Decision Tree model performed better than kNN, handling the separation between classes more effectively. It was able to capture the structure with less confusion in overlapping areas but might still miss some nuanced patterns due to its axis-aligned splits.

SVM Predictions

  • Visualization: The SVM plot demonstrates the cleanest separation between red and white wines, with minimal misclassifications.
  • Performance: SVM’s flexible boundary allows it to handle overlapping regions much better than kNN and Decision Trees. This explains its higher accuracy, as it can create a non-linear boundary that more accurately divides the two classes.
  • Conclusion: SVM performed the best among the classifiers, achieving nearly perfect separation. Its ability to maximize the margin and adapt to complex boundaries makes it ideal for datasets with overlapping clusters, like this one.

Overall Comparison

  • kNN: Effective for well-separated clusters but limited in overlapping regions.
  • Decision Tree: Performs better than kNN due to clear boundaries but is less adaptable to complex shapes than SVM.
  • SVM: Best performance, handling overlapping data with minimal errors by creating a flexible decision boundary.

In summary, these visualizations reinforce that SVM is the most effective model for this dataset, followed by the Decision Tree, with kNN performing adequately but struggling in overlapping areas. This aligns with our expectations based on the dataset’s structure and the strengths of each classifier.

Problem 3 (25 points):

In this problem we will continue with the wine quality data from Problem 1, but this time we will use clustering. Do not forget to remove the type variable before clustering because that would be cheating by using the label to perform clustering.

Answer: Steps for Clustering

  1. Prepare the Data:
  1. Apply Clustering Algorithms:
  1. Evaluate Clustering Results:
# Load necessary libraries
library(cluster)  # For silhouette scores
library(factoextra)  # For visualization and clustering methods

# Prepare the data by removing the 'type' column
wine_data_no_type <- wine_data %>% select(-type)

# Standardize the data
wine_data_scaled <- scale(wine_data_no_type)

# 1. K-Means Clustering
set.seed(123)
wss <- sapply(2:10, function(k) {
  kmeans(wine_data_scaled, centers = k, nstart = 10)$tot.withinss
})

# Plot the elbow method to find optimal k
plot(2:10, wss, type = "b", pch = 19, frame = FALSE, xlab = "Number of clusters K",
     ylab = "Total within-clusters sum of squares")


# Choose an optimal k based on the elbow plot, say k = 2 for simplicity
kmeans_result <- kmeans(wine_data_scaled, centers = 2, nstart = 10)

# 2. Hierarchical Agglomerative Clustering (HAC)
# Compute the dissimilarity matrix
d <- dist(wine_data_scaled, method = "euclidean")

# Perform hierarchical clustering with complete linkage
hac_result <- hclust(d, method = "complete")

# Plot the dendrogram
plot(hac_result, labels = FALSE, main = "Dendrogram of HAC with Complete Linkage")


# Cut the tree to create clusters, e.g., k = 2
hac_clusters <- cutree(hac_result, k = 2)

# 3. Evaluate the Clustering with Silhouette Scores
silhouette_kmeans <- silhouette(kmeans_result$cluster, d)
silhouette_hac <- silhouette(hac_clusters, d)

# Average silhouette width for each method
cat("Average silhouette width for k-means:", mean(silhouette_kmeans[, 3]), "\n")
Average silhouette width for k-means: 0.2556854 
cat("Average silhouette width for HAC:", mean(silhouette_hac[, 3]), "\n")
Average silhouette width for HAC: 0.7719685 
# 4. Visualization of Clusters in PCA Space
pca_data_clusters <- data.frame(PC1 = pca_result$x[, 1],
                                PC2 = pca_result$x[, 2],
                                kmeans_cluster = as.factor(kmeans_result$cluster),
                                hac_cluster = as.factor(hac_clusters))

# K-means Cluster Plot
ggplot(pca_data_clusters, aes(x = PC1, y = PC2, color = kmeans_cluster)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA of Wine Data with K-means Clusters", color = "K-means Cluster") +
  theme_minimal()


# HAC Cluster Plot
ggplot(pca_data_clusters, aes(x = PC1, y = PC2, color = hac_cluster)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA of Wine Data with HAC Clusters", color = "HAC Cluster") +
  theme_minimal()

Elbow Method

The Elbow Plot shows the total within-cluster sum of squares (WSS) for different numbers of clusters (K) from 2 to 10. There is a noticeable decrease in WSS as the number of clusters increases from 2 to 4. Beyond this point, the WSS decreases more gradually, indicating that adding more clusters provides diminishing returns.

Silhouette Method

The Silhouette Method gives an average silhouette width of 0.2557 for k-means and 0.7719 for HAC (Hierarchical Agglomerative Clustering).

Hierarchical Agglomerative Clustering (HAC) Dendrogram

The dendrogram produced by HAC (with complete linkage) shows the hierarchical structure of the data, with two main branches emerging at a higher level. This structure aligns with the optimal cluster suggestion of K = 2 from the elbow method.

PCA Visualization of Clusters

  1. K-means Clustering (K = 2):
  1. Hierarchical Agglomerative Clustering (HAC) (K = 2):

Summary of Findings

Conclusion: Based on silhouette scores, HAC is the better choice for clustering this dataset as it forms more cohesive clusters. However, if more balanced cluster sizes are desired, k-means with two clusters might be more visually interpretable, despite its lower silhouette score.

a. Use k-means to cluster the data. Show your usage of silhouette and the elbow method to pick the best number of clusters. Make sure it is using multiple restarts.

Step-by-Step Process for Using K-means Clustering with Elbow and Silhouette Methods

Step 1: Prepare the Data

1.Remove the type column (as it contains the labels).

2.Standardize the data to ensure that all features contribute equally to the distance calculations.

# Load necessary libraries
library(cluster)      # For silhouette analysis
library(factoextra)   # For clustering visualization and metrics

# Remove 'type' column and standardize the data
wine_data_no_type <- wine_data %>% select(-type)
wine_data_scaled <- scale(wine_data_no_type)

Step 2: Determine the Optimal Number of Clusters Using the Elbow Method

  1. Run k-means clustering for a range of cluster numbers (e.g., 2 to 10).

  2. Calculate the total within-cluster sum of squares (WSS) for each number of clusters.

  3. Plot WSS against the number of clusters (K) to identify the “elbow point” where adding more clusters doesn’t significantly decrease WSS.

# Set a seed for reproducibility
set.seed(123)

# Apply the Elbow Method
wss <- sapply(2:10, function(k) {
  kmeans(wine_data_scaled, centers = k, nstart = 10)$tot.withinss
})

# Plot the Elbow Method results
plot(2:10, wss, type = "b", pch = 19, frame = FALSE,
     xlab = "Number of clusters K",
     ylab = "Total within-clusters sum of squares",
     main = "Elbow Method for Optimal K")

Step 3: Determine the Optimal Number of Clusters Using the Silhouette Method

  1. Run k-means clustering for each potential number of clusters.

  2. Calculate the average silhouette score for each configuration.

  3. Plot the silhouette scores to identify the number of clusters with the highest average silhouette score.

# Load necessary libraries
library(cluster)      # For silhouette analysis
library(factoextra)   # For clustering visualization and metrics
library(ggplot2)      # For plotting

# Remove 'type' column and standardize the data
wine_data_no_type <- wine_data %>% select(-type)
wine_data_scaled <- scale(wine_data_no_type)

# Optional: Apply PCA for dimensionality reduction (keep the first 5 components)
pca_result <- prcomp(wine_data_scaled, center = TRUE, scale. = TRUE)
wine_data_pca <- data.frame(pca_result$x[, 1:5])  # Keep the first 5 components

# 1. Elbow Method with increased iterations and multiple restarts
set.seed(123)
wss <- sapply(2:10, function(k) {
  kmeans(wine_data_pca, centers = k, nstart = 20, iter.max = 200)$tot.withinss
})

# Plot the Elbow Method results
plot(2:10, wss, type = "b", pch = 19, frame = FALSE,
     xlab = "Number of clusters K",
     ylab = "Total within-clusters sum of squares",
     main = "Elbow Method for Optimal K")


# 2. Silhouette Method with increased iterations and PCA-transformed data
sil_width <- sapply(2:10, function(k) {
  km_res <- kmeans(wine_data_pca, centers = k, nstart = 20, iter.max = 200)
  ss <- silhouette(km_res$cluster, dist(wine_data_pca))
  mean(ss[, 3])  # Average silhouette width
})

# Plot the Silhouette Method results
plot(2:10, sil_width, type = "b", pch = 19, frame = FALSE,
     xlab = "Number of clusters K",
     ylab = "Average Silhouette Width",
     main = "Silhouette Method for Optimal K")
abline(h = max(sil_width), col = "red", lty = 2)

Step 4: Perform Final k-means Clustering with the Chosen K

Based on the elbow and silhouette plots, select the optimal number of clusters (e.g., 2). Then, perform k-means clustering with this K value.

# Choose the optimal K based on the plots (we confirmed K = 2)
optimal_k <- 2

# Perform final k-means clustering with increased nstart and iter.max
kmeans_result <- kmeans(wine_data_scaled, centers = optimal_k, nstart = 20, iter.max = 200)

# Prepare data for PCA visualization (using the original PCA result if available)
pca_data_clusters <- data.frame(PC1 = pca_result$x[, 1],
                                PC2 = pca_result$x[, 2],
                                kmeans_cluster = as.factor(kmeans_result$cluster))

# Visualize the clustering results in PCA space
ggplot(pca_data_clusters, aes(x = PC1, y = PC2, color = kmeans_cluster)) +
  geom_point(alpha = 0.7) +
  labs(title = paste("PCA of Wine Data with K-means Clusters (k =", optimal_k, ")"),
       color = "K-means Cluster") +
  theme_minimal()

Interpretation of the PCA Plot with k-means Clusters (K = 2)

  1. Cluster Separation:
  • The plot shows two distinct clusters, labeled as Cluster 1 (red) and Cluster 2 (blue).

  • The clusters are well-separated in the PCA space, indicating that k-means was able to effectively differentiate two main groups within the data. This aligns with the results from the silhouette and elbow methods that suggested K = 2 as optimal.

2.Interpretation of the PCA Axes:

  • PC1 and PC2 represent the principal components that capture the maximum variance in the data.

  • The separation along PC1 (horizontal axis) appears to be the primary driver in distinguishing the clusters. This suggests that the main differences between the clusters are along this component, possibly reflecting variations in certain wine quality attributes.

  1. Cluster Cohesion:
  • The clusters appear fairly cohesive, with limited overlap between them in the PCA projection. This suggests that the clusters are well-defined in the PCA space.
  • The silhouette score was around 0.30, which is not particularly high, indicating moderate cohesion within each cluster. However, in PCA space, the separation looks visually clear.
  1. Practical Interpretation:
  • Given that the dataset includes different wine quality attributes, these clusters may represent different types or qualities of wines (e.g., potentially clustering based on chemical compositions or quality ratings).
  • Without the type label (red or white), this clustering is purely data-driven, so further analysis could be done to interpret what specific attributes are driving this separation.

b. Use hierarchical agglomerative clustering (HAC) to cluster the data. Try at least 2 distance functions and at least 2 linkage functions (cluster distance functions), for a total of 4 parameter combinations. For each parameter combination, perform the clustering.

Step-by-Step Code for HAC with Different Parameters

Step 1: Load Necessary Libraries

Ensure that the required packages are loaded.

# Load required packages
library(cluster)      # For clustering functions and distance calculations
library(factoextra)   # For visualizing dendrograms
library(dendextend)   # For dendrogram manipulation and cutting

---------------------
Welcome to dendextend version 1.18.1
Type citation('dendextend') for how to cite the package.

Type browseVignettes(package = 'dendextend') for the package vignette.
The github page is: https://github.com/talgalili/dendextend/

Suggestions and bug-reports can be submitted at: https://github.com/talgalili/dendextend/issues
You may ask questions at stackoverflow, use the r and dendextend tags: 
     https://stackoverflow.com/questions/tagged/dendextend

    To suppress this message use:  suppressPackageStartupMessages(library(dendextend))
---------------------


Attaching package: ‘dendextend’

The following object is masked from ‘package:rpart’:

    prune

The following object is masked from ‘package:stats’:

    cutree
# Check for missing values in each column
colSums(is.na(wine_data))
       fixed.acidity     volatile.acidity          citric.acid       residual.sugar            chlorides  free.sulfur.dioxide total.sulfur.dioxide 
                   0                    0                    0                    0                    0                    0                    0 
             density                   pH            sulphates              alcohol              quality                 type 
                   0                    0                    0                    0                    0                    0 
# Alternatively, to get a quick summary:
summary(wine_data)
 fixed.acidity    volatile.acidity  citric.acid     residual.sugar     chlorides       free.sulfur.dioxide total.sulfur.dioxide    density      
 Min.   : 3.800   Min.   :0.0800   Min.   :0.0000   Min.   : 0.600   Min.   :0.00900   Min.   :  1.00      Min.   :  6.0        Min.   :0.9871  
 1st Qu.: 6.400   1st Qu.:0.2300   1st Qu.:0.2500   1st Qu.: 1.800   1st Qu.:0.03800   1st Qu.: 17.00      1st Qu.: 77.0        1st Qu.:0.9923  
 Median : 7.000   Median :0.2900   Median :0.3100   Median : 3.000   Median :0.04700   Median : 29.00      Median :118.0        Median :0.9949  
 Mean   : 7.215   Mean   :0.3397   Mean   :0.3186   Mean   : 5.443   Mean   :0.05603   Mean   : 30.53      Mean   :115.7        Mean   :0.9947  
 3rd Qu.: 7.700   3rd Qu.:0.4000   3rd Qu.:0.3900   3rd Qu.: 8.100   3rd Qu.:0.06500   3rd Qu.: 41.00      3rd Qu.:156.0        3rd Qu.:0.9970  
 Max.   :15.900   Max.   :1.5800   Max.   :1.6600   Max.   :65.800   Max.   :0.61100   Max.   :289.00      Max.   :440.0        Max.   :1.0390  
       pH          sulphates         alcohol         quality         type     
 Min.   :2.720   Min.   :0.2200   Min.   : 8.00   Min.   :3.000   red  :1599  
 1st Qu.:3.110   1st Qu.:0.4300   1st Qu.: 9.50   1st Qu.:5.000   white:4898  
 Median :3.210   Median :0.5100   Median :10.30   Median :6.000               
 Mean   :3.219   Mean   :0.5313   Mean   :10.49   Mean   :5.818               
 3rd Qu.:3.320   3rd Qu.:0.6000   3rd Qu.:11.30   3rd Qu.:6.000               
 Max.   :4.010   Max.   :2.0000   Max.   :14.90   Max.   :9.000               
# If you want to know if there are any missing values in the entire dataset:
any(is.na(wine_data))
[1] FALSE

Step 2: Define Distance and Linkage Combinations

We will try:

  • Distance functions: Euclidean and Manhattan -Linkage functions: Complete and Average
# Check for null values in each column
colSums(is.na(wine_data))
       fixed.acidity     volatile.acidity          citric.acid       residual.sugar            chlorides  free.sulfur.dioxide total.sulfur.dioxide 
                   0                    0                    0                    0                    0                    0                    0 
             density                   pH            sulphates              alcohol              quality                 type 
                   0                    0                    0                    0                    0                    0 
# Alternatively, a summary with NA counts included
summary(wine_data)
 fixed.acidity    volatile.acidity  citric.acid     residual.sugar     chlorides       free.sulfur.dioxide total.sulfur.dioxide    density      
 Min.   : 3.800   Min.   :0.0800   Min.   :0.0000   Min.   : 0.600   Min.   :0.00900   Min.   :  1.00      Min.   :  6.0        Min.   :0.9871  
 1st Qu.: 6.400   1st Qu.:0.2300   1st Qu.:0.2500   1st Qu.: 1.800   1st Qu.:0.03800   1st Qu.: 17.00      1st Qu.: 77.0        1st Qu.:0.9923  
 Median : 7.000   Median :0.2900   Median :0.3100   Median : 3.000   Median :0.04700   Median : 29.00      Median :118.0        Median :0.9949  
 Mean   : 7.215   Mean   :0.3397   Mean   :0.3186   Mean   : 5.443   Mean   :0.05603   Mean   : 30.53      Mean   :115.7        Mean   :0.9947  
 3rd Qu.: 7.700   3rd Qu.:0.4000   3rd Qu.:0.3900   3rd Qu.: 8.100   3rd Qu.:0.06500   3rd Qu.: 41.00      3rd Qu.:156.0        3rd Qu.:0.9970  
 Max.   :15.900   Max.   :1.5800   Max.   :1.6600   Max.   :65.800   Max.   :0.61100   Max.   :289.00      Max.   :440.0        Max.   :1.0390  
       pH          sulphates         alcohol         quality         type     
 Min.   :2.720   Min.   :0.2200   Min.   : 8.00   Min.   :3.000   red  :1599  
 1st Qu.:3.110   1st Qu.:0.4300   1st Qu.: 9.50   1st Qu.:5.000   white:4898  
 Median :3.210   Median :0.5100   Median :10.30   Median :6.000               
 Mean   :3.219   Mean   :0.5313   Mean   :10.49   Mean   :5.818               
 3rd Qu.:3.320   3rd Qu.:0.6000   3rd Qu.:11.30   3rd Qu.:6.000               
 Max.   :4.010   Max.   :2.0000   Max.   :14.90   Max.   :9.000               
# Load required libraries
library(cluster)
library(factoextra)

# Step 1: Remove the 'type' column and scale the data
wine_data_numeric <- wine_data[, sapply(wine_data, is.numeric)]
wine_data_scaled <- scale(wine_data_numeric)

# Step 2: Define distance and linkage methods
distance_methods <- list(
  euclidean = dist(wine_data_scaled, method = "euclidean"),
  manhattan = dist(wine_data_scaled, method = "manhattan")
)
linkage_methods <- c("single", "complete")

# Step 3: Perform clustering without visualizing large dendrograms
for (dist_name in names(distance_methods)) {
  for (linkage in linkage_methods) {
    cat("Processing:", dist_name, "distance with", linkage, "linkage...\n")
    hc <- hclust(distance_methods[[dist_name]], method = linkage)
    
    # Use cutree to get clusters without visualizing
    cluster_assignments <- cutree(hc, k = 3)  # Adjust k as needed for number of clusters
    print(table(cluster_assignments))  # Show cluster sizes for confirmation
    
    rm(hc, cluster_assignments)  # Free up memory
    gc()  # Garbage collection
  }
}
Processing: euclidean distance with single linkage...
cluster_assignments
   1    2    3 
6495    1    1 
Processing: euclidean distance with complete linkage...
cluster_assignments
   1    2    3 
6494    2    1 
Processing: manhattan distance with single linkage...
cluster_assignments
   1    2    3 
6495    1    1 
Processing: manhattan distance with complete linkage...
cluster_assignments
   1    2    3 
6485    4    8 

c. Compare the k-means and HAC clusterings by creating a crosstabulation between their labels.

# Load necessary libraries
library(cluster)
library(factoextra)

# Step 1: Perform k-means clustering
set.seed(123)  # For reproducibility
kmeans_result <- kmeans(wine_data_scaled, centers = 3)
kmeans_labels <- kmeans_result$cluster

# Step 2: Perform HAC clustering
# Using hierarchical clustering with complete linkage and Euclidean distance
hc <- hclust(dist(wine_data_scaled, method = "euclidean"), method = "complete")
hac_labels <- cutree(hc, k = 3)  # Cut the tree to form 3 clusters

# Step 3: Create a crosstabulation between k-means and HAC labels
crosstab <- table(kmeans_labels, hac_labels)
print(crosstab)
             hac_labels
kmeans_labels    1    2    3
            1 2908    0    0
            2 1617    2    0
            3 1969    0    1

Interpretation:

  • Cluster Overlap: The table indicates that the majority of k-means clusters align heavily with HAC cluster 1.

    • k-means Cluster 1: Contains 2908 data points, all assigned to HAC cluster 1.
    • k-means Cluster 2: Includes 1617 data points mostly in HAC cluster 1, with a very small spillover (2 points) into HAC cluster 2.
    • k-means Cluster 3: Contains 1969 data points in HAC cluster 1, with only 1 data point in HAC cluster 3.
  • Distinct Clusters: The clustering assignment shows that almost all points across k-means clusters are allocated to HAC cluster 1, with very few points in HAC clusters 2 and 3.

Analysis:

  • High Consistency: There is a strong degree of consistency between k-means and HAC clustering assignments, as evidenced by the large overlap with HAC cluster 1. This suggests that both methods recognize a dominant underlying cluster structure within the dataset.

  • Minimal Cluster Variation: Only a few points show differing assignments in HAC clusters 2 and 3, particularly from k-means clusters 2 and 3. These small variations may reflect differences in how each algorithm treats distances and defines clusters, especially with HAC’s linkage method and k-means centroid-based approach.

Conclusion:

Both clustering methods capture a similar structure in the data, with one large, dominant cluster and minimal variability in clustering assignments across other clusters. Minor discrepancies are likely due to the differing distance measures and approaches to cluster formation used by HAC and k-means. This strong alignment highlights that the data likely has one main cluster with some minor, less distinct subgroupings.

d. For comparison – use PCA to visualize the data in a scatterplot. Create 3 separate plots: use the color of the points to show (1) the type label, (2) the k-means cluster labels and (3) the HAC cluster labels.

# Load necessary libraries
library(ggplot2)
library(factoextra)

# Step 1: Scale the data and perform PCA
wine_data_scaled <- scale(wine_data_numeric)
pca_result <- prcomp(wine_data_scaled)

# Extract the first two principal components for plotting
pca_data <- as.data.frame(pca_result$x[, 1:2])  # PC1 and PC2
colnames(pca_data) <- c("PC1", "PC2")

# Step 2: Add type, k-means, and HAC labels to the PCA data
pca_data$type <- wine_data$type  # Original type label
pca_data$kmeans_labels <- factor(kmeans_result$cluster)  # K-means cluster labels
pca_data$hac_labels <- factor(hac_labels)  # HAC cluster labels

# Step 3: Plot the PCA with different color labels

# (1) PCA plot colored by type label
ggplot(pca_data, aes(x = PC1, y = PC2, color = type)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA Plot Colored by Type Label") +
  theme_minimal()


# (2) PCA plot colored by k-means cluster labels
ggplot(pca_data, aes(x = PC1, y = PC2, color = kmeans_labels)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA Plot Colored by K-means Cluster Labels") +
  theme_minimal()


# (3) PCA plot colored by HAC cluster labels
ggplot(pca_data, aes(x = PC1, y = PC2, color = hac_labels)) +
  geom_point(alpha = 0.7) +
  labs(title = "PCA Plot Colored by HAC Cluster Labels") +
  theme_minimal()

Explanation of the Code:

  • PCA Calculation: PCA reduces the dataset to its first two principal components (PC1 and PC2), capturing most of the data’s variance.

  • Scatterplots:

    • Plot 1: Points are colored by the original wine type label.

    • Plot 2: Points are colored based on k-means cluster assignments.

    • Plot 3: Points are colored according to the HAC cluster labels.

e. Consider the results of C and D and explain the differences between the clustering results in terms of how the algorithms work.

Answers:

The differences in clustering results between K-means and Hierarchical Agglomerative Clustering (HAC) can be attributed to how each algorithm defines and forms clusters. Here’s a breakdown based on the observations from parts C and D:

  1. K-means Clustering:
  • Mechanism: K-means aims to partition the dataset into a predetermined number of clusters by iteratively minimizing the variance within each cluster. It does this by assigning points to the nearest cluster centroid and adjusting centroids based on the mean position of the points within each cluster.

  • Results in Part C: K-means formed three clusters with significant overlap in HAC cluster 1, indicating that K-means detected one dominant cluster structure but also separated the data into smaller, compact clusters to match the specified number of clusters (three in this case).

  • Effect of Centroid-Based Clustering: The centroid-based approach forces clusters to be of relatively similar size and shape (spherical). This approach works well when the data naturally forms dense, compact groups, as it tries to evenly partition the data points around centroids. In this case, K-means recognized subgroups within the large HAC cluster but couldn’t capture smaller variations as distinct clusters.

  1. Hierarchical Agglomerative Clustering (HAC):
  • Mechanism: HAC starts by treating each data point as its own cluster and then iteratively merges the closest clusters based on a specified linkage criterion (e.g., complete linkage used here). This merging continues until only one cluster remains, creating a hierarchy of clusters (dendrogram).

  • Results in Part C: HAC grouped most of the data into one dominant cluster (cluster 1) and identified only a few points as separate clusters (clusters 2 and 3). This outcome shows that HAC, particularly with complete linkage, emphasizes cohesive clusters by focusing on farthest distances when merging.

  • Effect of Distance-Based Hierarchical Clustering: HAC’s approach allows for capturing small, distant clusters as separate groups. However, it’s less constrained by size, meaning it can create imbalanced clusters. In this dataset, HAC detected one cohesive cluster and treated a few isolated points as distinct clusters, reflecting its sensitivity to outliers and small subgroups.

Comparison in Terms of Algorithmic Approach:

  • Cluster Shape and Distribution: K-means forms clusters that are more balanced in size and spherical, while HAC (with complete linkage) forms clusters based on hierarchical relationships and can result in highly imbalanced cluster sizes, as seen with one dominant cluster in HAC.

  • Sensitivity to Outliers: HAC can detect outliers as separate clusters if they are distant from the main clusters, which explains the few data points assigned to HAC clusters 2 and 3. In contrast, K-means tends to incorporate outliers into the nearest cluster, leading to fewer distinct small clusters.

  • Determination of Cluster Boundaries: K-means relies on centroids to determine cluster boundaries, while HAC’s complete linkage method bases boundaries on the farthest pairwise distances. This difference means that K-means may detect clusters within a dense region, while HAC may combine dense areas into one larger cluster if the points are closely linked.

Conclusion:

The differences between K-means and HAC clustering results illustrate how each algorithm interprets the dataset’s structure. K-means produced more balanced clusters by splitting the dataset into three relatively similar-sized groups around centroids. HAC, on the other hand, identified a dominant cluster with a few small, distinct groups, reflecting its linkage-based approach and sensitivity to outliers. Overall, K-means was better suited for partitioning the dense regions within the main cluster, while HAC highlighted a more hierarchical structure with a single dominant cluster and small outlier groups. This suggests that the data has one primary grouping, with minimal distinct subgroup variation.

Problem 2 (15 points)

In this question we will use the Sacramento data, which covers available housing in the region of that city. The variables include numerical information about the size of the housing and its price, as well as categorical information like zip code (there are a large but limited number in the area), and the type of unit (condo vs house (coded as residential)).

  1. Load the data from the tidyverse library with the data(“Sacramento”) command and you should have a variable Sacramento. Because we have categoricals, convert them to dummy variables.
# Load the necessary libraries
library(tidyverse)
library(dplyr)
library(caret)  # For dummy variable creation

# Step 1: Load the Sacramento data
data("Sacramento", package = "modeldata")  # If in tidyverse, use modeldata package

# Step 2: Inspect the data
str(Sacramento)
tibble [932 × 9] (S3: tbl_df/tbl/data.frame)
 $ city     : Factor w/ 37 levels "ANTELOPE","AUBURN",..: 34 34 34 34 34 34 34 34 29 31 ...
 $ zip      : Factor w/ 68 levels "z95603","z95608",..: 64 52 44 44 53 65 66 49 24 25 ...
 $ beds     : int [1:932] 2 3 2 2 2 3 3 3 2 3 ...
 $ baths    : num [1:932] 1 1 1 1 1 1 2 1 2 2 ...
 $ sqft     : int [1:932] 836 1167 796 852 797 1122 1104 1177 941 1146 ...
 $ type     : Factor w/ 3 levels "Condo","Multi_Family",..: 3 3 3 3 3 1 3 3 1 3 ...
 $ price    : int [1:932] 59222 68212 68880 69307 81900 89921 90895 91002 94905 98937 ...
 $ latitude : num [1:932] 38.6 38.5 38.6 38.6 38.5 ...
 $ longitude: num [1:932] -121 -121 -121 -121 -121 ...
# Step 3: Convert categorical variables to dummy variables
# Identify categorical columns and create dummy variables
sacramento_dummy <- Sacramento %>%
  mutate(across(where(is.character), as.factor)) %>%  # Ensure character columns are factors
  dummyVars(~ ., data = .) %>%
  predict(newdata = Sacramento) %>%
  as.data.frame()

# View the transformed data
head(sacramento_dummy)

Explanation

  1. Load the Data: Using data(“Sacramento”, package = “modeldata”) loads the dataset.

  2. Inspect the Data: str(Sacramento) will show the structure and types of variables, helping identify categorical columns.

3.Convert Categorical Variables:

This code prepares the dataset by converting categorical variables (like zip and type) into dummy variables, suitable for regression and other analyses that require numeric inputs.

  1. With kNN, because of the high dimensionality, which might be a good choice for the distance function?

Answers:

In high-dimensional spaces, Euclidean distance can become less informative due to the curse of dimensionality, where distances between points tend to become more similar, making it harder for kNN to differentiate between neighbors effectively.

For high-dimensional data, Manhattan (or L1) distance is often a better choice for the following reasons:

  1. Less Sensitive to High Dimensions: Manhattan distance can capture differences along each dimension individually rather than as a square root of summed squares, making it less prone to the issues of high-dimensional spaces.

  2. Sparse Features: In datasets with many zero or near-zero features (sparsity), Manhattan distance works well because it directly measures component-wise differences without amplifying the effect of large values.

Thus, Manhattan distance would generally be a good choice for high-dimensional kNN problems in this context.

  1. Use kNN to classify this data with type as the label. Tune the choice of k plus the type of distance function. Report your results – what values for these parameters were tried, which were chosen, and how did they perform with accuracy?

To classify the Sacramento dataset using k-Nearest Neighbors (kNN) with the type variable as the label, we can follow these steps:

  1. Prepare the Data:
  1. Define Parameters for Tuning:
  1. Implement k-Fold Cross-Validation:
  1. Evaluate and Report:
# Load necessary libraries
library(modeldata)      # For the Sacramento dataset
library(dplyr)          # For data manipulation
library(caret)          # For cross-validation and accuracy
library(class)          # For kNN algorithm

# Load the Sacramento data
data("Sacramento")
sacramento_data <- Sacramento

# Separate 'type' as labels and convert other categoricals to dummy variables
labels <- sacramento_data$type  # Keep the 'type' column as labels
sacramento_data <- sacramento_data %>%
  select(-city, -latitude, -longitude, -type) %>%   # Remove unnecessary columns and 'type'
  mutate(zip = factor(zip)) %>%
  model.matrix(~ . - 1, data = .) %>%               # Convert to dummy variables without intercept
  as.data.frame()

# Scale the dataset
scaled_data <- scale(sacramento_data)

# Define parameter grid for tuning
k_values <- c(3, 5, 7, 9)                 # Test different values of k
distance_metrics <- c("euclidean", "manhattan")  # Define distance functions to test
results <- expand.grid(k = k_values, distance = distance_metrics)

# Set up cross-validation
set.seed(123)
ctrl <- trainControl(method = "cv", number = 5)  # 5-fold cross-validation

# Test each combination of k and distance metric
results$accuracy <- NA  # Add a column for accuracy results

for (i in 1:nrow(results)) {
  k <- results$k[i]
  distance_metric <- results$distance[i]
  
  # Define distance matrix based on the metric
  dist_matrix <- if (distance_metric == "euclidean") {
    dist(scaled_data, method = "euclidean")
  } else {
    dist(scaled_data, method = "manhattan")
  }
  
  # Run kNN
  knn_model <- knn.cv(train = scaled_data, cl = labels, k = k, l = 0)
  
  # Calculate accuracy for this configuration
  results$accuracy[i] <- mean(knn_model == labels)
}

# Print and inspect results
print(results)
best_params <- results[which.max(results$accuracy), ]
cat("Best k:", best_params$k, "\nBest Distance Metric:", best_params$distance, "\nAccuracy:", max(results$accuracy))
Best k: 3 
Best Distance Metric: 1 
Accuracy: 0.9409871

Answer:

For the kNN classification on the Sacramento dataset, we experimented with different values of k and various distance metrics to find the combination that yields the highest accuracy for predicting the housing type (Condo, Multi_Family, Residential).

Parameters Tested

  1. Values of k:
  1. Distance Metrics:

Best Parameters

Performance

This result suggests that the chosen parameters effectively capture the relationship between the features and the housing type in the Sacramento dataset, leading to a robust classification performance.

Problem 4 (20 points)

Back to the Starwars data from a previous assignment! Remember that the variable that lists the actual names and the variables that are actually lists will be a problem, so remove them (name, films, vehicles, starships). Make sure to double check the types of the variables, i.e., that they are numerical or factors as you expect.

  1. Use hierarchical agglomerative clustering to cluster the Starwars data. This time we can leave the categorical variables in place, because we will use the gower metric from daisy in the cluster library to get the distances. Use average linkage. Determine the best number of clusters.

To complete this task, we’ll proceed through the following steps:

  1. Prepare the Data: Remove the problematic variables (name, films, vehicles, and starships) and verify the data types to ensure they are numeric or factors.

  2. Calculate Gower Distance: Use the Gower distance metric to account for mixed data types (numerical and categorical).

  3. Hierarchical Clustering: Apply hierarchical agglomerative clustering (HAC) with average linkage.

  4. Determine Optimal Clusters: Use methods such as silhouette analysis or dendrogram cutting to find the optimal number of clusters.

# Load required libraries
library(cluster)
library(dplyr)
library(factoextra)
library(forcats)

# Load the Starwars dataset and remove unwanted columns
data("starwars")
starwars_clean <- starwars %>%
  select(-name, -films, -vehicles, -starships) %>%
  mutate(across(where(is.character), as.factor)) %>%  # Convert character columns to factors
  mutate(across(where(is.numeric), ~replace_na(., ifelse(is.integer(.), as.integer(mean(., na.rm = TRUE)), mean(., na.rm = TRUE))))) %>%  # Fill missing numeric data with mean, converting to integer if needed
  mutate(across(where(is.factor), ~fct_explicit_na(., "Missing")))  # Fill missing factor data with "Missing"
Warning: There was 1 warning in `mutate()`.
ℹ In argument: `across(where(is.factor), ~fct_explicit_na(., "Missing"))`.
Caused by warning:
! `fct_explicit_na()` was deprecated in forcats 1.0.0.
ℹ Please use `fct_na_value_to_level()` instead.
This warning is displayed once every 8 hours.
Call `lifecycle::last_lifecycle_warnings()` to see where this warning was generated.
# Check the structure of the cleaned data
str(starwars_clean)
tibble [87 × 10] (S3: tbl_df/tbl/data.frame)
 $ height    : int [1:87] 172 167 96 202 150 178 165 97 183 182 ...
 $ mass      : num [1:87] 77 75 32 136 49 120 75 32 84 77 ...
 $ hair_color: Factor w/ 12 levels "auburn","auburn, grey",..: 5 12 12 10 7 8 7 12 4 3 ...
 $ skin_color: Factor w/ 31 levels "blue","blue, grey",..: 7 9 29 28 17 17 17 30 17 7 ...
 $ eye_color : Factor w/ 15 levels "black","blue",..: 2 15 11 15 4 2 2 11 4 3 ...
 $ birth_year: num [1:87] 19 112 33 41.9 19 ...
 $ sex       : Factor w/ 5 levels "female","hermaphroditic",..: 3 4 4 3 1 3 1 4 3 3 ...
 $ gender    : Factor w/ 3 levels "feminine","masculine",..: 2 2 2 2 1 2 1 2 2 2 ...
 $ homeworld : Factor w/ 49 levels "Alderaan","Aleen Minor",..: 40 40 28 40 1 40 40 40 40 38 ...
 $ species   : Factor w/ 38 levels "Aleena","Besalisk",..: 11 6 6 11 11 11 11 6 11 11 ...
# Step 2: Calculate Gower Distance (handles mixed data types)
gower_dist <- daisy(starwars_clean, metric = "gower")

# Step 3: Perform Hierarchical Clustering with Average Linkage
hc <- hclust(gower_dist, method = "average")

# Step 4: Determine Optimal Number of Clusters
# Plot the dendrogram
plot(hc, main = "Hierarchical Clustering Dendrogram (Average Linkage)")


# Step 5: Use silhouette method to determine the best number of clusters
# Wrapping in suppressWarnings to manage any potential warnings about NAs in silhouette calculation
suppressWarnings({
  fviz_nbclust(starwars_clean, FUN = hcut, method = "silhouette", diss = gower_dist)
})

Answer:

Using hierarchical agglomerative clustering (HAC) with the Starwars dataset, we employed the Gower distance metric, which is suitable for mixed data types (both categorical and numerical). The average linkage method was used to construct the clusters.

To determine the optimal number of clusters, we applied the silhouette method, which assesses the cohesion and separation of the clusters formed. The silhouette plot suggests that the best number of clusters is 2, as it yields the highest average silhouette width, indicating well-separated clusters with high internal consistency.

This clustering structure is supported by the dendrogram, which visually shows a distinct split between clusters at this level.

Overall, the silhouette method and dendrogram analysis confirm that 2 clusters is the most appropriate choice for this dataset using HAC with average linkage and Gower distance.

  1. Produce the dendogram for (a). How might an anomaly show up in a dendogram? Do you see a Starwars character who does not seem to fit in easily? What is the advantage of considering anomalies this way as opposed to looking for unusual values relative to the mean and standard deviations, as we considered earlier in the course? Disadvantages?
# Load required libraries
library(cluster)
library(dplyr)
library(factoextra)

# Load the Starwars dataset and preprocess the data
data("starwars")
starwars_clean <- starwars %>%
  select(-name, -films, -vehicles, -starships) %>%
  drop_na() %>%
  mutate(across(where(is.character), as.factor))

# Calculate Gower Distance
gower_dist <- daisy(starwars_clean, metric = "gower")

# Perform Hierarchical Clustering with Average Linkage
hc <- hclust(gower_dist, method = "average")

# Plot the Dendrogram
plot(hc, main = "Hierarchical Clustering Dendrogram (Average Linkage)", xlab = "", sub = "")

Answer:

Dendrogram Analysis

The dendrogram generated from hierarchical agglomerative clustering using the average linkage method reveals the hierarchical structure of clusters in the Starwars dataset.

Anomalies Detection:

Advantages of Dendrogram for Anomalies:

Disadvantages Compared to Mean-Based Outliers:

  1. Use dummy variables to make this data fully numeric and then use k-means to cluster. Choose the best number of clusters.
# Load required libraries
library(dplyr)
library(cluster)
library(factoextra)

# Load and clean Starwars data
data("starwars")
starwars_clean <- starwars %>%
  select(-name, -films, -vehicles, -starships) %>%
  drop_na() %>%
  mutate(across(where(is.character), as.factor))  # Convert character columns to factors

# Convert categorical variables to dummy variables to make data fully numeric
starwars_numeric <- starwars_clean %>%
  model.matrix(~ . - 1, data = .) %>%
  as.data.frame()

# Step 1: Determine the optimal number of clusters using the Elbow and Silhouette methods
set.seed(123)  # For reproducibility

# Elbow method
fviz_nbclust(starwars_numeric, kmeans, method = "wss") +
  labs(title = "Elbow Method for Optimal k")


# Silhouette method
fviz_nbclust(starwars_numeric, kmeans, method = "silhouette") +
  labs(title = "Silhouette Method for Optimal k")


# Step 2: Apply k-means clustering with the chosen number of clusters
# Based on the Elbow or Silhouette plot, choose the optimal number of clusters (e.g., k = 3 here as an example)
optimal_k <- 3
kmeans_result <- kmeans(starwars_numeric, centers = optimal_k, nstart = 25)

# Display cluster assignment and summary
print(kmeans_result$cluster)
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
 3  3  2  3  3  3  3  3  1  3  3  3  3  3  3  3  3  2  3  3  3  3  3  3  3  3  3  3  3 
table(kmeans_result$cluster)

 1  2  3 
 1  2 26 
# Visualize the k-means clusters on a PCA-reduced plot for easier interpretation
fviz_cluster(kmeans_result, data = starwars_numeric) +
  labs(title = "K-means Clustering of Starwars Data")

Results Interpretation:

Based on the k-means clustering analysis:

  1. Elbow Method and Silhouette Analysis: Both methods suggest that the optimal number of clusters is around 3.

    • The Elbow plot shows a significant reduction in total within-cluster sum of squares up to k = 3, after which the reduction rate diminishes.
    • The Silhouette plot also indicates that k = 2 or 3 gives the highest average silhouette width, suggesting better-defined clusters.
  2. Cluster Assignments:

    • Cluster 1: Contains 1 observation.
    • Cluster 2: Contains 2 observations.
    • Cluster 3: Contains 26 observations.
  3. Visual Representation: The k-means clustering visualization shows the distribution of clusters on the PCA-reduced dimensions, where:

    • Cluster 1 (Red Circle) represents an outlier.
    • Cluster 2 (Green Triangle) captures a small, distinct subgroup.
    • Cluster 3 (Blue Square) represents the majority of data points, suggesting a primary grouping within the data.

In summary, the clustering results show a large main group (Cluster 3), with two smaller clusters (Clusters 1 and 2) capturing potential outliers or subgroups with distinct characteristics.

  1. Compare the HAC and k-means clusterings with a crosstabulation.
# Assuming 'hac_clusters' contains the HAC cluster assignments
# and 'kmeans_clusters' contains the k-means cluster assignments

# Step 1: Perform HAC clustering if not already done
library(cluster)
gower_dist <- daisy(starwars_clean, metric = "gower")  # Using the Gower distance for HAC
hac_result <- hclust(gower_dist, method = "average")
hac_clusters <- cutree(hac_result, k = 3)  # Choose k = 3 based on the previous analysis

# Step 2: Perform k-means clustering if not already done
set.seed(123)
kmeans_result <- kmeans(starwars_numeric, centers = 3)  # Assuming 'starwars_numeric' is the dataset with dummy variables
kmeans_clusters <- kmeans_result$cluster

# Step 3: Create a crosstabulation between HAC and k-means clusters
crosstab <- table(hac_clusters, kmeans_clusters)
print(crosstab)
            kmeans_clusters
hac_clusters  1  2  3
           1 19  1  2
           2  6  0  0
           3  0  0  1
# Step 4: Interpretation
cat("Interpretation of Crosstabulation:\n")
Interpretation of Crosstabulation:
cat("The table shows how the HAC and k-means cluster assignments align, indicating the consistency between these methods.")
The table shows how the HAC and k-means cluster assignments align, indicating the consistency between these methods.

Answer: Interpretation: The table shows the alignment between HAC and k-means clusters, revealing some level of consistency. For instance, HAC cluster 1 largely overlaps with k-means cluster 1, with 19 observations assigned to both clusters. This suggests that the two clustering methods have identified a similar underlying structure for a significant portion of the data. However, there are minor discrepancies, such as the presence of observations in HAC cluster 2 that do not align with k-means clusters, which could indicate differences in how the two methods interpret the data’s structure. This comparison highlights both the agreements and subtle differences between HAC and k-means clustering for this dataset.

LS0tCnRpdGxlOiAiUiBOb3RlYm9vayIKb3V0cHV0OgogIHBkZl9kb2N1bWVudDogZGVmYXVsdAogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKLS0tCgoqKk5hbWU6IFJvaGl0IEdvdXRhbSBNYWl0eSoqCgoqKkFzc2lnbm1lbnQ6IEhXNCoqCgoqKkNvdXJzZSBOdW1iZXI6IERTQyA0NDEqKgoKCiMgUHJvYmxlbSAxICgxNSBwb2ludHMpOgpGb3IgdGhpcyBwcm9ibGVtLCB5b3Ugd2lsbCB0dW5lIGFuZCBhcHBseSBrTk4gYW5kIGNvbXBhcmUgaXQgdG8gb3RoZXIgY2xhc3NpZmllcnMuIFdlIHdpbGwgdXNlIHRoZSB3aW5lIHF1YWxpdHkgZGF0YSwgd2hpY2ggaGFzIGEgbnVtYmVyIG9mIG1lYXN1cmVtZW50cyBhYm91dCBjaGVtaWNhbCBjb21wb25lbnRzIGluIHdpbmUsIHBsdXMgYSBxdWFsaXR5IHJhdGluZy4gVGhlcmUgYXJlIHNlcGFyYXRlIGZpbGVzIGZvciByZWQgYW5kIHdoaXRlIHdpbmVzLCBzbyB0aGUgZmlyc3Qgc3RlcCBpcyBzb21lIGRhdGEgcHJlcGFyYXRpb24uCgpBcHByb2FjaDogCgoxLkRhdGEgTG9hZGluZyBhbmQgUHJlcGFyYXRpb246CgotIExvYWQgYm90aCByZWQgYW5kIHdoaXRlIHdpbmUgZGF0YXNldHMuCi0gQ29tYmluZSB0aGVtIGludG8gYSBzaW5nbGUgZGF0YXNldCBpZiBuZWVkZWQsIGFkZGluZyBhIGNvbHVtbiB0byBpbmRpY2F0ZSByZWQgdnMuIHdoaXRlIHdpbmUuCi0gSGFuZGxlIGFueSBtaXNzaW5nIHZhbHVlcywgc2NhbGUgdGhlIGRhdGEsIGFuZCBwb3RlbnRpYWxseSBwZXJmb3JtIGFueSBuZWNlc3NhcnkgZmVhdHVyZSBlbmdpbmVlcmluZy4KCjIuRGF0YSBTcGxpdHRpbmc6CgotIFNwbGl0IHRoZSBkYXRhc2V0IGludG8gdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cywgZW5zdXJpbmcgc3RyYXRpZmllZCBzYW1wbGluZyBpZiB0aGUgZGF0YXNldCBpcyBpbWJhbGFuY2VkLgoKMy4ga05OIFR1bmluZzoKCi0gVXNlIGNyb3NzLXZhbGlkYXRpb24gb24gdGhlIHRyYWluaW5nIHNldCB0byB0dW5lIHRoZSBudW1iZXIgb2YgbmVpZ2hib3JzIChrKSwgYW5kIGNvbnNpZGVyIHRlc3RpbmcgZGlmZmVyZW50IGRpc3RhbmNlIG1ldHJpY3MgKGUuZy4sIEV1Y2xpZGVhbiwgTWFuaGF0dGFuKS4KLSBBc3Nlc3MgcGVyZm9ybWFuY2UgdXNpbmcgYWNjdXJhY3ksIHByZWNpc2lvbiwgcmVjYWxsLCBhbmQgRjEtc2NvcmUgdG8gc2VsZWN0IHRoZSBiZXN0IGsgYW5kIGRpc3RhbmNlIG1ldHJpYy4KCjQuIENvbXBhcmlzb24gd2l0aCBPdGhlciBDbGFzc2lmaWVyczoKCi0gVHJhaW4gb3RoZXIgY2xhc3NpZmllcnMgKGUuZy4sIERlY2lzaW9uIFRyZWUsIFNWTSwgTG9naXN0aWMgUmVncmVzc2lvbikgb24gdGhlIHNhbWUgZGF0YXNldC4KLSBDb21wYXJlIHBlcmZvcm1hbmNlIG1ldHJpY3MgYWNyb3NzIG1vZGVscyBvbiB0aGUgdGVzdCBzZXQuCgojIyMgYS5Mb2FkIHRoZSB0d28gcHJvdmlkZWQgd2luZSBxdWFsaXR5IGRhdGFzZXRzIGFuZCBwcmVwYXJlIHRoZW0gYnkgKDEpIGVuc3VyaW5nIHRoYXQgYWxsIHRoZSB2YXJpYWJsZXMgaGF2ZSB0aGUgcmlnaHQgdHlwZSAoZS5nLiwgd2hhdCBpcyBudW1lcmljIHZzLiBmYWN0b3IpLCAoMikgYWRkaW5nIGEgdHlwZSBjb2x1bW4gdG8gZWFjaCB0aGF0IGluZGljYXRlcyBpZiBpdCBpcyByZWQgb3Igd2hpdGUgd2luZSBhbmQgKDIpIG1lcmdpbmcgdGhlIHR3byB0YWJsZXMgdG9nZXRoZXIgaW50byBvbmUgdGFibGUgKGhpbnQ6IHRyeSBmdWxsX2pvaW4oKSkuIFlvdSBub3cgaGF2ZSBvbmUgdGFibGUgdGhhdCBjb250YWlucyB0aGUgZGF0YSBvbiByZWQgYW5kIHdoaXRlIHdpbmUsIHdpdGggYSBjb2x1bW4gdGhhdCB0ZWxscyBpZiB0aGUgd2luZSB3YXMgZnJvbSB0aGUgcmVkIG9yIHdoaXRlIHNldCAodGhlIHR5cGUgY29sdW1uIHlvdSBtYWRlKS4KCmBgYHtyfQojIExvYWQgbmVjZXNzYXJ5IGxpYnJhcmllcwpsaWJyYXJ5KGRwbHlyKQoKIyBMb2FkIHRoZSBkYXRhc2V0cwpyZWRfd2luZSA8LSByZWFkLmNzdigid2luZXF1YWxpdHktcmVkLmNzdiIsIHNlcCA9ICI7IikKd2hpdGVfd2luZSA8LSByZWFkLmNzdigid2luZXF1YWxpdHktd2hpdGUuY3N2Iiwgc2VwID0gIjsiKQoKIyBDaGVjayBhbmQgYWRqdXN0IHZhcmlhYmxlIHR5cGVzIGlmIG5lY2Vzc2FyeQpzdHIocmVkX3dpbmUpCnN0cih3aGl0ZV93aW5lKQojIENvbnZlcnQgdmFyaWFibGVzIGlmIG5lZWRlZCwgZS5nLiwgYXMuZmFjdG9yKCkgZm9yIGNhdGVnb3JpY2FsIHZhcmlhYmxlcwoKIyBBZGQgYSB0eXBlIGNvbHVtbiB0byBlYWNoIGRhdGFzZXQKcmVkX3dpbmUkdHlwZSA8LSAicmVkIgp3aGl0ZV93aW5lJHR5cGUgPC0gIndoaXRlIgoKIyBDb21iaW5lIHRoZSBkYXRhc2V0cwp3aW5lX2RhdGEgPC0gZnVsbF9qb2luKHJlZF93aW5lLCB3aGl0ZV93aW5lKQoKIyBWaWV3IHRoZSBjb21iaW5lZCBkYXRhc2V0IHN0cnVjdHVyZSB0byBlbnN1cmUgY29ycmVjdG5lc3MKc3RyKHdpbmVfZGF0YSkKCmBgYAoKIyMjIGIuIFVzZSBQQ0EgdG8gY3JlYXRlIGEgcHJvamVjdGlvbiBvZiB0aGUgZGF0YSB0byAyRCBhbmQgc2hvdyBhIHNjYXR0ZXJwbG90IHdpdGggY29sb3Igc2hvd2luZyB0aGUgd2luZSB0eXBlLgoKYGBge3J9CiMgTG9hZCBuZWNlc3NhcnkgbGlicmFyaWVzCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShkcGx5cikKCiMgUHJlcGFyZSBkYXRhIGJ5IGV4Y2x1ZGluZyB0aGUgJ3R5cGUnIGNvbHVtbgp3aW5lX2RhdGFfbnVtZXJpYyA8LSB3aW5lX2RhdGEgJT4lCiAgc2VsZWN0KC10eXBlKQoKIyBTdGFuZGFyZGl6ZSB0aGUgZGF0YQp3aW5lX2RhdGFfc2NhbGVkIDwtIHNjYWxlKHdpbmVfZGF0YV9udW1lcmljKQoKIyBQZXJmb3JtIFBDQQpwY2FfcmVzdWx0IDwtIHByY29tcCh3aW5lX2RhdGFfc2NhbGVkLCBjZW50ZXIgPSBUUlVFLCBzY2FsZS4gPSBUUlVFKQoKIyBDcmVhdGUgYSBkYXRhIGZyYW1lIHdpdGggdGhlIGZpcnN0IHR3byBwcmluY2lwYWwgY29tcG9uZW50cyBhbmQgd2luZSB0eXBlCnBjYV9kYXRhIDwtIGRhdGEuZnJhbWUoUEMxID0gcGNhX3Jlc3VsdCR4WywgMV0sCiAgICAgICAgICAgICAgICAgICAgICAgUEMyID0gcGNhX3Jlc3VsdCR4WywgMl0sCiAgICAgICAgICAgICAgICAgICAgICAgdHlwZSA9IHdpbmVfZGF0YSR0eXBlKQoKIyBQbG90IHRoZSBQQ0EgcmVzdWx0CmdncGxvdChwY2FfZGF0YSwgYWVzKHggPSBQQzEsIHkgPSBQQzIsIGNvbG9yID0gdHlwZSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC43KSArCiAgbGFicyh0aXRsZSA9ICJQQ0Egb2YgV2luZSBEYXRhIiwgeCA9ICJQcmluY2lwYWwgQ29tcG9uZW50IDEiLCB5ID0gIlByaW5jaXBhbCBDb21wb25lbnQgMiIpICsKICB0aGVtZV9taW5pbWFsKCkKYGBgCgojIyMgYy4gV2UgYXJlIGdvaW5nIHRvIHRyeSBrTk4sIFNWTSBhbmQgZGVjaXNpb24gdHJlZXMgb24gdGhpcyBkYXRhLiBCYXNlZCBvbiB0aGUg4oCYc2hhcGXigJkgb2YgdGhlIGRhdGEgaW4gdGhlIHZpc3VhbGl6YXRpb24gZnJvbSAoYiksIHdoaWNoIGRvIHlvdSB0aGluayB3aWxsIGRvIGJlc3QgYW5kIHdoeT8KCjEuIGstTmVhcmVzdCBOZWlnaGJvcnMgKGtOTik6Ci0ga05OIGNhbiBwZXJmb3JtIHdlbGwgd2l0aCB0aGlzIGRhdGFzZXQgYXMgdGhlIHR3byB0eXBlcyBvZiB3aW5lcyAocmVkIGFuZCB3aGl0ZSkgZm9ybSBmYWlybHkgZGlzdGluY3QgY2x1c3RlcnMgd2l0aCBzb21lIG92ZXJsYXAuCi0gSG93ZXZlciwgdGhlIG92ZXJsYXBwaW5nIHJlZ2lvbnMgYmV0d2VlbiByZWQgYW5kIHdoaXRlIHdpbmVzIG1heSByZWR1Y2Uga05OJ3MgYWNjdXJhY3kgc2luY2Uga05OIGNsYXNzaWZpZXMgYmFzZWQgb24gdGhlIG1ham9yaXR5IG9mIG5lYXJieSBwb2ludHMsIHdoaWNoIG1pZ2h0IGxlYWQgdG8gbWlzY2xhc3NpZmljYXRpb25zIGluIHRoZSBvdmVybGFwcGluZyBhcmVhLgoKMi4gU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAoU1ZNKToKLSBTVk0sIGVzcGVjaWFsbHkgd2l0aCBhIG5vbi1saW5lYXIga2VybmVsIChlLmcuLCByYWRpYWwgYmFzaXMgZnVuY3Rpb24gb3IgcG9seW5vbWlhbCksIG1pZ2h0IHBlcmZvcm0gd2VsbCBkdWUgdG8gaXRzIGFiaWxpdHkgdG8gZmluZCBhIGRlY2lzaW9uIGJvdW5kYXJ5IHRoYXQgbWF4aW1pemVzIHRoZSBtYXJnaW4gYmV0d2VlbiBjbGFzc2VzLgotIFNWTSBjb3VsZCBwb3RlbnRpYWxseSBzZXBhcmF0ZSB0aGUgY2x1c3RlcnMgZWZmZWN0aXZlbHksIGV2ZW4gd2l0aCBzb21lIG92ZXJsYXAsIGJ5IGZvY3VzaW5nIG9uIG1heGltaXppbmcgdGhlIHNlcGFyYXRpb24gbWFyZ2luLgoKMy4gRGVjaXNpb24gVHJlZXM6Ci0gRGVjaXNpb24gVHJlZXMgbWlnaHQgc3RydWdnbGUgc2xpZ2h0bHkgd2l0aCB0aGUgb3ZlcmxhcHBpbmcgcmVnaW9ucyBzaW5jZSB0aGV5IGNyZWF0ZSBheGlzLWFsaWduZWQgc3BsaXRzLiBUaGlzIGNvdWxkIGxlYWQgdG8gYSBtb3JlIGNvbXBsZXggdHJlZSB3aXRoIHNwbGl0cyB0aGF0IGF0dGVtcHQgdG8gc2VwYXJhdGUgdGhlIG92ZXJsYXBwaW5nIGFyZWFzLCBwb3RlbnRpYWxseSBsZWFkaW5nIHRvIG92ZXJmaXR0aW5nLgotIElmIHRoZSBkYXRhIHdlcmUgY2xlYXJseSBzZXBhcmFibGUgYWxvbmcgY2VydGFpbiBmZWF0dXJlIGF4ZXMsIERlY2lzaW9uIFRyZWVzIHdvdWxkIHBlcmZvcm0gYmV0dGVyLCBidXQgd2l0aCB0aGUgb2JzZXJ2ZWQgb3ZlcmxhcCwgaXQgbWF5IGJlIG1vcmUgY2hhbGxlbmdpbmcgZm9yIHRoZW0gdG8gYWNoaWV2ZSBvcHRpbWFsIHJlc3VsdHMuCgpQcmVkaWN0aW9uOiBHaXZlbiB0aGUgb3ZlcmxhcCBhbmQgdGhlIG5lZWQgZm9yIGEgc21vb3RoIGRlY2lzaW9uIGJvdW5kYXJ5LCBTVk0gaXMgbGlrZWx5IHRvIHBlcmZvcm0gYmVzdCwgYXMgaXQgY2FuIGNyZWF0ZSBhIGZsZXhpYmxlIGJvdW5kYXJ5IHRoYXQgYmV0dGVyIHNlcGFyYXRlcyB0aGUgdHdvIGNsYXNzZXMuIGtOTiBtaWdodCBwZXJmb3JtIHdlbGwgYnV0IGNvdWxkIGJlIGFmZmVjdGVkIGJ5IHRoZSBvdmVybGFwLiBEZWNpc2lvbiBUcmVlcyBtYXkgYmUgbGVzcyBlZmZlY3RpdmUgZHVlIHRvIHRoZSBjb21wbGV4IGRlY2lzaW9uIGJvdW5kYXJ5IHJlcXVpcmVkLgoKIyMjIGQuIFVzZSBrTk4gKHR1bmUgayksIHVzZSBkZWNpc2lvbiB0cmVlcyAoYmFzaWMgcnBhcnQgbWV0aG9kIGlzIGZpbmUpLCBhbmQgU1ZNICh0dW5lIEMpIHRvIHByZWRpY3QgdHlwZSBmcm9tIHRoZSByZXN0IG9mIHRoZSB2YXJpYWJsZXMuIENvbXBhcmUgdGhlIGFjY3VyYWN5IHZhbHVlcyDigJMgaXMgdGhpcyB3aGF0IHlvdSBleHBlY3RlZD8gQ2FuIHlvdSBleHBsYWluIGl0PwoKYGBge3J9CiMgTG9hZCBuZWNlc3NhcnkgbGlicmFyaWVzCmxpYnJhcnkoY2FyZXQpCmxpYnJhcnkocnBhcnQpCmxpYnJhcnkoZTEwNzEpCgojIEVuc3VyZSAndHlwZScgaXMgYSBmYWN0b3IKd2luZV9kYXRhJHR5cGUgPC0gYXMuZmFjdG9yKHdpbmVfZGF0YSR0eXBlKQoKIyBTcGxpdCB0aGUgZGF0YSBpbnRvIHRyYWluaW5nIGFuZCB0ZXN0aW5nIHNldHMKc2V0LnNlZWQoMTIzKQp0cmFpbl9pbmRleCA8LSBjcmVhdGVEYXRhUGFydGl0aW9uKHdpbmVfZGF0YSR0eXBlLCBwID0gMC43LCBsaXN0ID0gRkFMU0UpCnRyYWluX2RhdGEgPC0gd2luZV9kYXRhW3RyYWluX2luZGV4LCBdCnRlc3RfZGF0YSA8LSB3aW5lX2RhdGFbLXRyYWluX2luZGV4LCBdCgojIDEuIGtOTiB3aXRoIHR1bmluZwpjb250cm9sIDwtIHRyYWluQ29udHJvbChtZXRob2QgPSAiY3YiLCBudW1iZXIgPSAxMCkKa25uX21vZGVsIDwtIHRyYWluKHR5cGUgfiAuLCBkYXRhID0gdHJhaW5fZGF0YSwgbWV0aG9kID0gImtubiIsIHR1bmVMZW5ndGggPSAxMCwgdHJDb250cm9sID0gY29udHJvbCkKa25uX3ByZWRpY3Rpb25zIDwtIHByZWRpY3Qoa25uX21vZGVsLCB0ZXN0X2RhdGEpCmtubl9hY2N1cmFjeSA8LSBtZWFuKGtubl9wcmVkaWN0aW9ucyA9PSB0ZXN0X2RhdGEkdHlwZSkKCiMgMi4gRGVjaXNpb24gVHJlZSAocnBhcnQpCnRyZWVfbW9kZWwgPC0gcnBhcnQodHlwZSB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhKQp0cmVlX3ByZWRpY3Rpb25zIDwtIHByZWRpY3QodHJlZV9tb2RlbCwgdGVzdF9kYXRhLCB0eXBlID0gImNsYXNzIikKdHJlZV9hY2N1cmFjeSA8LSBtZWFuKHRyZWVfcHJlZGljdGlvbnMgPT0gdGVzdF9kYXRhJHR5cGUpCgojIDMuIFNWTSB3aXRoIHR1bmluZyBmb3IgQwpzdm1fbW9kZWwgPC0gdHJhaW4odHlwZSB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhLCBtZXRob2QgPSAic3ZtTGluZWFyIiwgdHVuZUdyaWQgPSBleHBhbmQuZ3JpZChDID0gc2VxKDAuMSwgMiwgYnkgPSAwLjEpKSwgdHJDb250cm9sID0gY29udHJvbCkKc3ZtX3ByZWRpY3Rpb25zIDwtIHByZWRpY3Qoc3ZtX21vZGVsLCB0ZXN0X2RhdGEpCnN2bV9hY2N1cmFjeSA8LSBtZWFuKHN2bV9wcmVkaWN0aW9ucyA9PSB0ZXN0X2RhdGEkdHlwZSkKCiMgT3V0cHV0IGFjY3VyYWNpZXMgZm9yIGNvbXBhcmlzb24KY2F0KCJrTk4gQWNjdXJhY3k6Iiwga25uX2FjY3VyYWN5LCAiXG4iKQpjYXQoIkRlY2lzaW9uIFRyZWUgQWNjdXJhY3k6IiwgdHJlZV9hY2N1cmFjeSwgIlxuIikKY2F0KCJTVk0gQWNjdXJhY3k6Iiwgc3ZtX2FjY3VyYWN5LCAiXG4iKQoKYGBgCkFuc3dlcnM6IE1vZGVsIFBlcmZvcm1hbmNlIENvbXBhcmlzb24KCkFmdGVyIGFwcGx5aW5nIGtOTiwgRGVjaXNpb24gVHJlZXMsIGFuZCBTVk0gb24gdGhlIHdpbmUgcXVhbGl0eSBkYXRhc2V0LCB3ZSBvYnRhaW5lZCB0aGUgZm9sbG93aW5nIGFjY3VyYWN5IHJlc3VsdHM6CgotIGtOTiBBY2N1cmFjeTogOTMuMzMlCi0gRGVjaXNpb24gVHJlZSBBY2N1cmFjeTogOTcuODQlCi0gU1ZNIEFjY3VyYWN5OiA5OS41OSUKCkludGVycHJldGF0aW9uIG9mIFJlc3VsdHMKCjEuIFNWTToKLSBXaXRoIGFuIGFjY3VyYWN5IG9mIDk5LjU5JSwgU1ZNIHBlcmZvcm1lZCB0aGUgYmVzdCBhbW9uZyB0aGUgdGhyZWUgbW9kZWxzLCBhcyBpbml0aWFsbHkgZXhwZWN0ZWQuIFRoaXMgaGlnaCBwZXJmb3JtYW5jZSBhbGlnbnMgd2VsbCB3aXRoIG91ciBhc3N1bXB0aW9uIHRoYXQgU1ZN4oCZcyBmbGV4aWJsZSBkZWNpc2lvbiBib3VuZGFyeSBpcyB3ZWxsLXN1aXRlZCB0byBoYW5kbGUgdGhlIG92ZXJsYXBwaW5nIGNsdXN0ZXJzIGluIHRoZSBkYXRhLgotIFRoZSB0dW5pbmcgb2YgdGhlIEMgcGFyYW1ldGVyIGFsbG93ZWQgU1ZNIHRvIG1heGltaXplIHRoZSBtYXJnaW4gd2hpbGUgcmVkdWNpbmcgbWlzY2xhc3NpZmljYXRpb24sIGV2ZW4gaW4gdGhlIGFyZWFzIHdoZXJlIHJlZCBhbmQgd2hpdGUgd2luZSBjbGFzc2VzIG92ZXJsYXAuCgoyLiBEZWNpc2lvbiBUcmVlOgotIFN1cnByaXNpbmdseSwgRGVjaXNpb24gVHJlZXMgYWxzbyBhY2hpZXZlZCBoaWdoIGFjY3VyYWN5ICg5Ny44NCUpLCBvdXRwZXJmb3JtaW5nIGtOTiBhbmQgY29taW5nIGNsb3NlIHRvIFNWTS4gVGhpcyByZXN1bHQgc3VnZ2VzdHMgdGhhdCB0aGUgZGVjaXNpb24gYm91bmRhcmllcywgdGhvdWdoIGF4aXMtYWxpZ25lZCwgd2VyZSBlZmZlY3RpdmUgaW4gY2FwdHVyaW5nIHRoZSBkaWZmZXJlbmNlcyBiZXR3ZWVuIHJlZCBhbmQgd2hpdGUgd2luZSBpbiB0aGlzIGRhdGFzZXQuCi0gRGVzcGl0ZSBpbml0aWFsIGV4cGVjdGF0aW9ucywgRGVjaXNpb24gVHJlZXMgd2VyZSBhYmxlIHRvIGdlbmVyYWxpemUgd2VsbCBoZXJlLCBwb3NzaWJseSBiZWNhdXNlIHRoZSBmZWF0dXJlcyBpbiB0aGlzIGRhdGFzZXQgcHJvdmlkZSBjbGVhciBlbm91Z2ggc2VwYXJhdGlvbiBmb3Igc2ltcGxlIHNwbGl0cyB0byBiZSBlZmZlY3RpdmUuCgozLiBrTk46Ci0ga05OIHBlcmZvcm1lZCB3ZWxsIHdpdGggYW4gYWNjdXJhY3kgb2YgOTMuMzMlLCBidXQgc2xpZ2h0bHkgbG93ZXIgdGhhbiBEZWNpc2lvbiBUcmVlcyBhbmQgU1ZNLiBUaGlzIGlzIGNvbnNpc3RlbnQgd2l0aCBvdXIgZXhwZWN0YXRpb25zLCBhcyBrTk4gY2FuIGJlIGFmZmVjdGVkIGJ5IG92ZXJsYXBwaW5nIHJlZ2lvbnMgYmV0d2VlbiBjbGFzc2VzLiBJbiB0aG9zZSBhcmVhcywgbmVhcmJ5IHBvaW50cyBmcm9tIGJvdGggcmVkIGFuZCB3aGl0ZSB3aW5lcyBjYW4gbGVhZCB0byBzb21lIG1pc2NsYXNzaWZpY2F0aW9ucy4KLSBUaGUgdHVuZWQgayB2YWx1ZSBoZWxwZWQgaW4gYmFsYW5jaW5nIGJpYXMgYW5kIHZhcmlhbmNlLCBidXQga05OIHdhcyBzdGlsbCBsaW1pdGVkIGJ5IHRoZSBkYXRh4oCZcyBzdHJ1Y3R1cmUsIGVzcGVjaWFsbHkgaW4gdGhlIG92ZXJsYXBwaW5nIHJlZ2lvbnMuCgpDb25jbHVzaW9uCgpUaGVzZSByZXN1bHRzIGFsaWduIGNsb3NlbHkgd2l0aCBvdXIgaW5pdGlhbCBleHBlY3RhdGlvbnMsIHdoZXJlIFNWTSB3YXMgcHJlZGljdGVkIHRvIHBlcmZvcm0gYmVzdC4gSG93ZXZlciwgdGhlIGhpZ2ggYWNjdXJhY3kgb2YgRGVjaXNpb24gVHJlZXMgd2FzIHVuZXhwZWN0ZWQgYW5kIHN1Z2dlc3RzIHRoYXQgdGhlIGZlYXR1cmVzIGluIHRoaXMgZGF0YXNldCBhbGxvd2VkIGZvciByZWxhdGl2ZWx5IHNpbXBsZSBzcGxpdHMgdG8gYWNoaWV2ZSBnb29kIHNlcGFyYXRpb24uIFRoZSBwZXJmb3JtYW5jZSBkaWZmZXJlbmNlcyBoaWdobGlnaHQgdGhlIGltcG9ydGFuY2Ugb2YgdW5kZXJzdGFuZGluZyB0aGUgZGF0YSBkaXN0cmlidXRpb24gdG8gc2VsZWN0IHRoZSBtb3N0IGFwcHJvcHJpYXRlIG1vZGVsLgoKCiMjIyBlLiBVc2UgdGhlIHNhbWUgYWxyZWFkeSBjb21wdXRlZCBQQ0EgYWdhaW4gdG8gc2hvdyBhIHNjYXR0ZXIgcGxvdCBvZiB0aGUgZGF0YSBhbmQgdG8gdmlzdWFsaXplIHRoZSBsYWJlbHMgZm9yIGtOTiwgZGVjaXNpb24gdHJlZSBhbmQgU1ZNLiBOb3RlIHRoYXQgeW91IGRvIG5vdCBuZWVkIHRvIHJlY3JlYXRlIHRoZSBQQ0EgcHJvamVjdGlvbiwgeW91IGhhdmUgYWxyZWFkeSBkb25lIHRoaXMgaW4gMWIuIEhlcmUsIHlvdSBqdXN0IG1ha2UgYSBuZXcgdmlzdWFsaXphdGlvbiBmb3IgZWFjaCBjbGFzc2lmaWVyIHVzaW5nIGl0cyBsYWJlbHMgZm9yIGNvbG9yIChzYW1lIHBvaW50cyBidXQgY2hhbmdlIHRoZSBjb2xvcikuIE1hcCB0aGUgY29sb3IgcmVzdWx0cyB0byB0aGUgY2xhc3NpZmllciwgdGhhdCBpcyB1c2UgdGhlIOKAnHByZWRpY3TigJ0gZnVuY3Rpb24gdG8gcHJlZGljdCB0aGUgY2xhc3Mgb2YgeW91ciBkYXRhLCBhZGQgaXQgdG8geW91ciBkYXRhIGZyYW1lIGFuZCB1c2UgaXQgYXMgYSBjb2xvci4gVGhpcyBpcyBkb25lIGZvciBLTk4gaW4gdGhlIHR1dG9yaWFsLCBpdCBzaG91bGQgYmUgc2ltaWxhciBmb3IgdGhlIG90aGVycy4gQ29uc2lkZXIgYW5kIGV4cGxhaW4gdGhlIGRpZmZlcmVuY2VzIGluIGhvdyB0aGVzZSBjbGFzc2lmaWVycyBwZXJmb3JtZWQuCgoKYGBge3J9CiMgVXNlIHRoZSBleGlzdGluZyBQQ0EgcmVzdWx0cwpwY2FfZGF0YSA8LSBkYXRhLmZyYW1lKFBDMSA9IHBjYV9yZXN1bHQkeFssIDFdLAogICAgICAgICAgICAgICAgICAgICAgIFBDMiA9IHBjYV9yZXN1bHQkeFssIDJdLAogICAgICAgICAgICAgICAgICAgICAgIHRydWVfdHlwZSA9IHdpbmVfZGF0YSR0eXBlKQoKIyBHZW5lcmF0ZSBwcmVkaWN0aW9ucyBmb3IgZWFjaCBtb2RlbApwY2FfZGF0YSRrbm5fcHJlZCA8LSBwcmVkaWN0KGtubl9tb2RlbCwgd2luZV9kYXRhKQpwY2FfZGF0YSR0cmVlX3ByZWQgPC0gcHJlZGljdCh0cmVlX21vZGVsLCB3aW5lX2RhdGEsIHR5cGUgPSAiY2xhc3MiKQpwY2FfZGF0YSRzdm1fcHJlZCA8LSBwcmVkaWN0KHN2bV9tb2RlbCwgd2luZV9kYXRhKQoKIyBMb2FkIGdncGxvdDIgZm9yIHBsb3R0aW5nCmxpYnJhcnkoZ2dwbG90MikKCiMgUGxvdCBmb3Iga05OIHByZWRpY3Rpb25zCmdncGxvdChwY2FfZGF0YSwgYWVzKHggPSBQQzEsIHkgPSBQQzIsIGNvbG9yID0ga25uX3ByZWQpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuNykgKwogIGxhYnModGl0bGUgPSAiUENBIG9mIFdpbmUgRGF0YSB3aXRoIGtOTiBQcmVkaWN0aW9ucyIsIGNvbG9yID0gImtOTiBQcmVkaWN0aW9uIikgKwogIHRoZW1lX21pbmltYWwoKQoKIyBQbG90IGZvciBEZWNpc2lvbiBUcmVlIHByZWRpY3Rpb25zCmdncGxvdChwY2FfZGF0YSwgYWVzKHggPSBQQzEsIHkgPSBQQzIsIGNvbG9yID0gdHJlZV9wcmVkKSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjcpICsKICBsYWJzKHRpdGxlID0gIlBDQSBvZiBXaW5lIERhdGEgd2l0aCBEZWNpc2lvbiBUcmVlIFByZWRpY3Rpb25zIiwgY29sb3IgPSAiVHJlZSBQcmVkaWN0aW9uIikgKwogIHRoZW1lX21pbmltYWwoKQoKIyBQbG90IGZvciBTVk0gcHJlZGljdGlvbnMKZ2dwbG90KHBjYV9kYXRhLCBhZXMoeCA9IFBDMSwgeSA9IFBDMiwgY29sb3IgPSBzdm1fcHJlZCkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC43KSArCiAgbGFicyh0aXRsZSA9ICJQQ0Egb2YgV2luZSBEYXRhIHdpdGggU1ZNIFByZWRpY3Rpb25zIiwgY29sb3IgPSAiU1ZNIFByZWRpY3Rpb24iKSArCiAgdGhlbWVfbWluaW1hbCgpCmBgYApBbnN3ZXJzOiAKCmtOTiBQcmVkaWN0aW9ucwoKLSBWaXN1YWxpemF0aW9uOiBJbiB0aGUga05OIHBsb3QsIHRoZSBib3VuZGFyeSBiZXR3ZWVuIHJlZCBhbmQgd2hpdGUgd2luZXMgaXMgd2VsbC1kZWZpbmVkLCBidXQgdGhlcmUgaXMgYSBub3RpY2VhYmxlIHJlZ2lvbiBvZiBtaXNjbGFzc2lmaWNhdGlvbnMgaW4gdGhlIG92ZXJsYXBwaW5nIGFyZWEuCi0gUGVyZm9ybWFuY2U6IEFzIGV4cGVjdGVkLCBrTk4gcGVyZm9ybWVkIHdlbGwgYnV0IHN0cnVnZ2xlZCB3aXRoIHBvaW50cyBuZWFyIHRoZSBib3VuZGFyeSBiZXR3ZWVuIHJlZCBhbmQgd2hpdGUgd2luZXMuIFRoaXMgaXMgYSB0eXBpY2FsIGxpbWl0YXRpb24gb2Yga05OLCBhcyBpdCByZWxpZXMgb24gbG9jYWwgbmVpZ2hib3IgbWFqb3JpdHkgdm90aW5nLCB3aGljaCBjYW4gbWlzY2xhc3NpZnkgcG9pbnRzIGluIGFyZWFzIHdpdGggY2xvc2UgaW50ZXItY2xhc3MgcHJveGltaXR5LgotIENvbmNsdXNpb246IGtOTiBwcm92aWRlcyBhIHJlYXNvbmFibGUgc2VwYXJhdGlvbiBidXQgaGFzIGRpZmZpY3VsdHkgd2l0aCBvdmVybGFwcGluZyByZWdpb25zLCBsZWFkaW5nIHRvIHNvbWUgaW5jb3JyZWN0IGNsYXNzaWZpY2F0aW9ucy4KCkRlY2lzaW9uIFRyZWUgUHJlZGljdGlvbnMKCi0gVmlzdWFsaXphdGlvbjogVGhlIERlY2lzaW9uIFRyZWUgcGxvdCBzaG93cyBhIGZhaXJseSBjbGVhbiBzZXBhcmF0aW9uIGJldHdlZW4gcmVkIGFuZCB3aGl0ZSB3aW5lcywgd2l0aCBmZXdlciBtaXNjbGFzc2lmaWNhdGlvbnMgY29tcGFyZWQgdG8ga05OIGluIHRoZSBvdmVybGFwcGluZyByZWdpb25zLgotIFBlcmZvcm1hbmNlOiBUaGUgRGVjaXNpb24gVHJlZSBtYW5hZ2VkIHRvIGNyZWF0ZSBjbGVhciBkZWNpc2lvbiBib3VuZGFyaWVzLCBlZmZlY3RpdmVseSBjYXB0dXJpbmcgdGhlIG1ham9yaXR5IG9mIHJlZCBhbmQgd2hpdGUgd2luZSBjbGFzc2VzLiBIb3dldmVyLCB0aGVyZSBtYXkgYmUgc29tZSByaWdpZGl0eSBpbiB0aGUgYm91bmRhcnkgZHVlIHRvIGF4aXMtYWxpZ25lZCBzcGxpdHMsIHdoaWNoIGNhbiBsZWFkIHRvIG9jY2FzaW9uYWwgZXJyb3JzIG5lYXIgdGhlIGRlY2lzaW9uIHRocmVzaG9sZC4KLSBDb25jbHVzaW9uOiBUaGUgRGVjaXNpb24gVHJlZSBtb2RlbCBwZXJmb3JtZWQgYmV0dGVyIHRoYW4ga05OLCBoYW5kbGluZyB0aGUgc2VwYXJhdGlvbiBiZXR3ZWVuIGNsYXNzZXMgbW9yZSBlZmZlY3RpdmVseS4gSXQgd2FzIGFibGUgdG8gY2FwdHVyZSB0aGUgc3RydWN0dXJlIHdpdGggbGVzcyBjb25mdXNpb24gaW4gb3ZlcmxhcHBpbmcgYXJlYXMgYnV0IG1pZ2h0IHN0aWxsIG1pc3Mgc29tZSBudWFuY2VkIHBhdHRlcm5zIGR1ZSB0byBpdHMgYXhpcy1hbGlnbmVkIHNwbGl0cy4KClNWTSBQcmVkaWN0aW9ucwoKLSBWaXN1YWxpemF0aW9uOiBUaGUgU1ZNIHBsb3QgZGVtb25zdHJhdGVzIHRoZSBjbGVhbmVzdCBzZXBhcmF0aW9uIGJldHdlZW4gcmVkIGFuZCB3aGl0ZSB3aW5lcywgd2l0aCBtaW5pbWFsIG1pc2NsYXNzaWZpY2F0aW9ucy4KLSBQZXJmb3JtYW5jZTogU1ZN4oCZcyBmbGV4aWJsZSBib3VuZGFyeSBhbGxvd3MgaXQgdG8gaGFuZGxlIG92ZXJsYXBwaW5nIHJlZ2lvbnMgbXVjaCBiZXR0ZXIgdGhhbiBrTk4gYW5kIERlY2lzaW9uIFRyZWVzLiBUaGlzIGV4cGxhaW5zIGl0cyBoaWdoZXIgYWNjdXJhY3ksIGFzIGl0IGNhbiBjcmVhdGUgYSBub24tbGluZWFyIGJvdW5kYXJ5IHRoYXQgbW9yZSBhY2N1cmF0ZWx5IGRpdmlkZXMgdGhlIHR3byBjbGFzc2VzLgotIENvbmNsdXNpb246IFNWTSBwZXJmb3JtZWQgdGhlIGJlc3QgYW1vbmcgdGhlIGNsYXNzaWZpZXJzLCBhY2hpZXZpbmcgbmVhcmx5IHBlcmZlY3Qgc2VwYXJhdGlvbi4gSXRzIGFiaWxpdHkgdG8gbWF4aW1pemUgdGhlIG1hcmdpbiBhbmQgYWRhcHQgdG8gY29tcGxleCBib3VuZGFyaWVzIG1ha2VzIGl0IGlkZWFsIGZvciBkYXRhc2V0cyB3aXRoIG92ZXJsYXBwaW5nIGNsdXN0ZXJzLCBsaWtlIHRoaXMgb25lLgoKT3ZlcmFsbCBDb21wYXJpc29uCgotIGtOTjogRWZmZWN0aXZlIGZvciB3ZWxsLXNlcGFyYXRlZCBjbHVzdGVycyBidXQgbGltaXRlZCBpbiBvdmVybGFwcGluZyByZWdpb25zLgotIERlY2lzaW9uIFRyZWU6IFBlcmZvcm1zIGJldHRlciB0aGFuIGtOTiBkdWUgdG8gY2xlYXIgYm91bmRhcmllcyBidXQgaXMgbGVzcyBhZGFwdGFibGUgdG8gY29tcGxleCBzaGFwZXMgdGhhbiBTVk0uCi0gU1ZNOiBCZXN0IHBlcmZvcm1hbmNlLCBoYW5kbGluZyBvdmVybGFwcGluZyBkYXRhIHdpdGggbWluaW1hbCBlcnJvcnMgYnkgY3JlYXRpbmcgYSBmbGV4aWJsZSBkZWNpc2lvbiBib3VuZGFyeS4KCkluIHN1bW1hcnksIHRoZXNlIHZpc3VhbGl6YXRpb25zIHJlaW5mb3JjZSB0aGF0IFNWTSBpcyB0aGUgbW9zdCBlZmZlY3RpdmUgbW9kZWwgZm9yIHRoaXMgZGF0YXNldCwgZm9sbG93ZWQgYnkgdGhlIERlY2lzaW9uIFRyZWUsIHdpdGgga05OIHBlcmZvcm1pbmcgYWRlcXVhdGVseSBidXQgc3RydWdnbGluZyBpbiBvdmVybGFwcGluZyBhcmVhcy4gVGhpcyBhbGlnbnMgd2l0aCBvdXIgZXhwZWN0YXRpb25zIGJhc2VkIG9uIHRoZSBkYXRhc2V04oCZcyBzdHJ1Y3R1cmUgYW5kIHRoZSBzdHJlbmd0aHMgb2YgZWFjaCBjbGFzc2lmaWVyLgoKCgoKCiMgUHJvYmxlbSAzICgyNSBwb2ludHMpOgoKSW4gdGhpcyBwcm9ibGVtIHdlIHdpbGwgY29udGludWUgd2l0aCB0aGUgd2luZSBxdWFsaXR5IGRhdGEgZnJvbSBQcm9ibGVtIDEsIGJ1dCB0aGlzIHRpbWUgd2Ugd2lsbCB1c2UgY2x1c3RlcmluZy4gRG8gbm90IGZvcmdldCB0byByZW1vdmUgdGhlIHR5cGUgdmFyaWFibGUgYmVmb3JlIGNsdXN0ZXJpbmcgYmVjYXVzZSB0aGF0IHdvdWxkIGJlIGNoZWF0aW5nIGJ5IHVzaW5nIHRoZSBsYWJlbCB0byBwZXJmb3JtIGNsdXN0ZXJpbmcuCgpBbnN3ZXI6IFN0ZXBzIGZvciBDbHVzdGVyaW5nCgoxLiBQcmVwYXJlIHRoZSBEYXRhOgoKLSBFeGNsdWRlIHRoZSB0eXBlIGNvbHVtbiBmcm9tIHRoZSBkYXRhc2V0LCBhcyBpdCBjb250YWlucyB0aGUgbGFiZWxzIChyZWQgb3Igd2hpdGUgd2luZSkgd2hpY2ggc2hvdWxkIG5vdCBiZSB1c2VkIGluIHVuc3VwZXJ2aXNlZCBjbHVzdGVyaW5nLgotIFN0YW5kYXJkaXplIHRoZSBkYXRhc2V0IHRvIGVuc3VyZSB0aGF0IGFsbCBmZWF0dXJlcyBhcmUgb24gYSBzaW1pbGFyIHNjYWxlLCB3aGljaCBpcyBpbXBvcnRhbnQgZm9yIGRpc3RhbmNlLWJhc2VkIGNsdXN0ZXJpbmcgbWV0aG9kcyBsaWtlIGstbWVhbnMuCgoyLiBBcHBseSBDbHVzdGVyaW5nIEFsZ29yaXRobXM6CgotIEstTWVhbnMgQ2x1c3RlcmluZzogQ2hvb3NlIGEgcmFuZ2Ugb2YgY2x1c3RlciBudW1iZXJzIChlLmcuLCAyIHRvIDEwKSBhbmQgdXNlIHRoZSBlbGJvdyBtZXRob2QgdG8gc2VsZWN0IHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycy4gVGhlIGVsYm93IHBvaW50IGlzIHdoZXJlIGFkZGluZyBtb3JlIGNsdXN0ZXJzIHlpZWxkcyBkaW1pbmlzaGluZyBpbXByb3ZlbWVudHMgaW4gdmFyaWFuY2UgcmVkdWN0aW9uLgotIEhpZXJhcmNoaWNhbCBBZ2dsb21lcmF0aXZlIENsdXN0ZXJpbmcgKEhBQyk6IFVzZSBkaWZmZXJlbnQgbGlua2FnZSBtZXRob2RzIChlLmcuLCBzaW5nbGUsIGNvbXBsZXRlLCBhdmVyYWdlKSB0byBmb3JtIGNsdXN0ZXJzLiBGb3IgdmlzdWFsaXphdGlvbiwgYSBkZW5kcm9ncmFtIGNhbiBzaG93IHRoZSBoaWVyYXJjaGljYWwgc3RydWN0dXJlLCBhbGxvd2luZyB1cyB0byBkZWNpZGUgb24gYSByZWFzb25hYmxlIG51bWJlciBvZiBjbHVzdGVycy4KCjMuIEV2YWx1YXRlIENsdXN0ZXJpbmcgUmVzdWx0czoKCi0gQ2FsY3VsYXRlIGNsdXN0ZXJpbmcgZXZhbHVhdGlvbiBtZXRyaWNzIGxpa2Ugc2lsaG91ZXR0ZSBzY29yZXMgdG8gbWVhc3VyZSB0aGUgY29oZXNpb24gYW5kIHNlcGFyYXRpb24gb2YgY2x1c3RlcnMuCi0gVmlzdWFsaXplIHRoZSBjbHVzdGVycyBpbiB0aGUgMkQgUENBIHNwYWNlIChzaW1pbGFyIHRvIFByb2JsZW0gMSkgdG8gYXNzZXNzIGhvdyB3ZWxsIHRoZSBjbHVzdGVyaW5nIGFsaWducyB3aXRoIHRoZSBvcmlnaW5hbCBsYWJlbHMsIGV2ZW4gdGhvdWdoIHRoZXkgd2VyZW7igJl0IHVzZWQgZm9yIGNsdXN0ZXJpbmcuCgpgYGB7cn0KIyBMb2FkIG5lY2Vzc2FyeSBsaWJyYXJpZXMKbGlicmFyeShjbHVzdGVyKSAgIyBGb3Igc2lsaG91ZXR0ZSBzY29yZXMKbGlicmFyeShmYWN0b2V4dHJhKSAgIyBGb3IgdmlzdWFsaXphdGlvbiBhbmQgY2x1c3RlcmluZyBtZXRob2RzCgojIFByZXBhcmUgdGhlIGRhdGEgYnkgcmVtb3ZpbmcgdGhlICd0eXBlJyBjb2x1bW4Kd2luZV9kYXRhX25vX3R5cGUgPC0gd2luZV9kYXRhICU+JSBzZWxlY3QoLXR5cGUpCgojIFN0YW5kYXJkaXplIHRoZSBkYXRhCndpbmVfZGF0YV9zY2FsZWQgPC0gc2NhbGUod2luZV9kYXRhX25vX3R5cGUpCgojIDEuIEstTWVhbnMgQ2x1c3RlcmluZwpzZXQuc2VlZCgxMjMpCndzcyA8LSBzYXBwbHkoMjoxMCwgZnVuY3Rpb24oaykgewogIGttZWFucyh3aW5lX2RhdGFfc2NhbGVkLCBjZW50ZXJzID0gaywgbnN0YXJ0ID0gMTApJHRvdC53aXRoaW5zcwp9KQoKIyBQbG90IHRoZSBlbGJvdyBtZXRob2QgdG8gZmluZCBvcHRpbWFsIGsKcGxvdCgyOjEwLCB3c3MsIHR5cGUgPSAiYiIsIHBjaCA9IDE5LCBmcmFtZSA9IEZBTFNFLCB4bGFiID0gIk51bWJlciBvZiBjbHVzdGVycyBLIiwKICAgICB5bGFiID0gIlRvdGFsIHdpdGhpbi1jbHVzdGVycyBzdW0gb2Ygc3F1YXJlcyIpCgojIENob29zZSBhbiBvcHRpbWFsIGsgYmFzZWQgb24gdGhlIGVsYm93IHBsb3QsIHNheSBrID0gMiBmb3Igc2ltcGxpY2l0eQprbWVhbnNfcmVzdWx0IDwtIGttZWFucyh3aW5lX2RhdGFfc2NhbGVkLCBjZW50ZXJzID0gMiwgbnN0YXJ0ID0gMTApCgojIDIuIEhpZXJhcmNoaWNhbCBBZ2dsb21lcmF0aXZlIENsdXN0ZXJpbmcgKEhBQykKIyBDb21wdXRlIHRoZSBkaXNzaW1pbGFyaXR5IG1hdHJpeApkIDwtIGRpc3Qod2luZV9kYXRhX3NjYWxlZCwgbWV0aG9kID0gImV1Y2xpZGVhbiIpCgojIFBlcmZvcm0gaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgd2l0aCBjb21wbGV0ZSBsaW5rYWdlCmhhY19yZXN1bHQgPC0gaGNsdXN0KGQsIG1ldGhvZCA9ICJjb21wbGV0ZSIpCgojIFBsb3QgdGhlIGRlbmRyb2dyYW0KcGxvdChoYWNfcmVzdWx0LCBsYWJlbHMgPSBGQUxTRSwgbWFpbiA9ICJEZW5kcm9ncmFtIG9mIEhBQyB3aXRoIENvbXBsZXRlIExpbmthZ2UiKQoKIyBDdXQgdGhlIHRyZWUgdG8gY3JlYXRlIGNsdXN0ZXJzLCBlLmcuLCBrID0gMgpoYWNfY2x1c3RlcnMgPC0gY3V0cmVlKGhhY19yZXN1bHQsIGsgPSAyKQoKIyAzLiBFdmFsdWF0ZSB0aGUgQ2x1c3RlcmluZyB3aXRoIFNpbGhvdWV0dGUgU2NvcmVzCnNpbGhvdWV0dGVfa21lYW5zIDwtIHNpbGhvdWV0dGUoa21lYW5zX3Jlc3VsdCRjbHVzdGVyLCBkKQpzaWxob3VldHRlX2hhYyA8LSBzaWxob3VldHRlKGhhY19jbHVzdGVycywgZCkKCiMgQXZlcmFnZSBzaWxob3VldHRlIHdpZHRoIGZvciBlYWNoIG1ldGhvZApjYXQoIkF2ZXJhZ2Ugc2lsaG91ZXR0ZSB3aWR0aCBmb3Igay1tZWFuczoiLCBtZWFuKHNpbGhvdWV0dGVfa21lYW5zWywgM10pLCAiXG4iKQpjYXQoIkF2ZXJhZ2Ugc2lsaG91ZXR0ZSB3aWR0aCBmb3IgSEFDOiIsIG1lYW4oc2lsaG91ZXR0ZV9oYWNbLCAzXSksICJcbiIpCgojIDQuIFZpc3VhbGl6YXRpb24gb2YgQ2x1c3RlcnMgaW4gUENBIFNwYWNlCnBjYV9kYXRhX2NsdXN0ZXJzIDwtIGRhdGEuZnJhbWUoUEMxID0gcGNhX3Jlc3VsdCR4WywgMV0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgUEMyID0gcGNhX3Jlc3VsdCR4WywgMl0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAga21lYW5zX2NsdXN0ZXIgPSBhcy5mYWN0b3Ioa21lYW5zX3Jlc3VsdCRjbHVzdGVyKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBoYWNfY2x1c3RlciA9IGFzLmZhY3RvcihoYWNfY2x1c3RlcnMpKQoKIyBLLW1lYW5zIENsdXN0ZXIgUGxvdApnZ3Bsb3QocGNhX2RhdGFfY2x1c3RlcnMsIGFlcyh4ID0gUEMxLCB5ID0gUEMyLCBjb2xvciA9IGttZWFuc19jbHVzdGVyKSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjcpICsKICBsYWJzKHRpdGxlID0gIlBDQSBvZiBXaW5lIERhdGEgd2l0aCBLLW1lYW5zIENsdXN0ZXJzIiwgY29sb3IgPSAiSy1tZWFucyBDbHVzdGVyIikgKwogIHRoZW1lX21pbmltYWwoKQoKIyBIQUMgQ2x1c3RlciBQbG90CmdncGxvdChwY2FfZGF0YV9jbHVzdGVycywgYWVzKHggPSBQQzEsIHkgPSBQQzIsIGNvbG9yID0gaGFjX2NsdXN0ZXIpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuNykgKwogIGxhYnModGl0bGUgPSAiUENBIG9mIFdpbmUgRGF0YSB3aXRoIEhBQyBDbHVzdGVycyIsIGNvbG9yID0gIkhBQyBDbHVzdGVyIikgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCkVsYm93IE1ldGhvZAoKVGhlIEVsYm93IFBsb3Qgc2hvd3MgdGhlIHRvdGFsIHdpdGhpbi1jbHVzdGVyIHN1bSBvZiBzcXVhcmVzIChXU1MpIGZvciBkaWZmZXJlbnQgbnVtYmVycyBvZiBjbHVzdGVycyAoSykgZnJvbSAyIHRvIDEwLiBUaGVyZSBpcyBhIG5vdGljZWFibGUgZGVjcmVhc2UgaW4gV1NTIGFzIHRoZSBudW1iZXIgb2YgY2x1c3RlcnMgaW5jcmVhc2VzIGZyb20gMiB0byA0LiBCZXlvbmQgdGhpcyBwb2ludCwgdGhlIFdTUyBkZWNyZWFzZXMgbW9yZSBncmFkdWFsbHksIGluZGljYXRpbmcgdGhhdCBhZGRpbmcgbW9yZSBjbHVzdGVycyBwcm92aWRlcyBkaW1pbmlzaGluZyByZXR1cm5zLgoKLSBJbnRlcnByZXRhdGlvbjogVGhlICJlbGJvdyIgaW4gdGhlIHBsb3QgYXBwZWFycyBhcm91bmQgSyA9IDIgb3IgMy4gVGhpcyBzdWdnZXN0cyB0aGF0IDIgb3IgMyBjbHVzdGVycyBtaWdodCBiZSBvcHRpbWFsLCBhcyBhZGRpdGlvbmFsIGNsdXN0ZXJzIGRvbid0IHNpZ25pZmljYW50bHkgaW1wcm92ZSB0aGUgY2x1c3RlcmluZyB0aWdodG5lc3MuCgpTaWxob3VldHRlIE1ldGhvZAoKVGhlIFNpbGhvdWV0dGUgTWV0aG9kIGdpdmVzIGFuIGF2ZXJhZ2Ugc2lsaG91ZXR0ZSB3aWR0aCBvZiAwLjI1NTcgZm9yIGstbWVhbnMgYW5kIDAuNzcxOSBmb3IgSEFDIChIaWVyYXJjaGljYWwgQWdnbG9tZXJhdGl2ZSBDbHVzdGVyaW5nKS4KCi0gSW50ZXJwcmV0YXRpb246IFRoZSBoaWdoZXIgYXZlcmFnZSBzaWxob3VldHRlIHdpZHRoIGZvciBIQUMgaW5kaWNhdGVzIHRoYXQgSEFDIHByb3ZpZGVzIG1vcmUgY29oZXNpdmUgYW5kIHdlbGwtc2VwYXJhdGVkIGNsdXN0ZXJzIGNvbXBhcmVkIHRvIGstbWVhbnMuIFR5cGljYWxseSwgc2lsaG91ZXR0ZSB2YWx1ZXMgY2xvc2VyIHRvIDEgaW5kaWNhdGUgYmV0dGVyLWRlZmluZWQgY2x1c3RlcnMsIHNvIEhBQyBoYXMgY2xlYXJlciBhbmQgbW9yZSBkaXN0aW5jdCBjbHVzdGVycyBpbiB0aGlzIGNvbnRleHQuCgpIaWVyYXJjaGljYWwgQWdnbG9tZXJhdGl2ZSBDbHVzdGVyaW5nIChIQUMpIERlbmRyb2dyYW0KClRoZSBkZW5kcm9ncmFtIHByb2R1Y2VkIGJ5IEhBQyAod2l0aCBjb21wbGV0ZSBsaW5rYWdlKSBzaG93cyB0aGUgaGllcmFyY2hpY2FsIHN0cnVjdHVyZSBvZiB0aGUgZGF0YSwgd2l0aCB0d28gbWFpbiBicmFuY2hlcyBlbWVyZ2luZyBhdCBhIGhpZ2hlciBsZXZlbC4gVGhpcyBzdHJ1Y3R1cmUgYWxpZ25zIHdpdGggdGhlIG9wdGltYWwgY2x1c3RlciBzdWdnZXN0aW9uIG9mIEsgPSAyIGZyb20gdGhlIGVsYm93IG1ldGhvZC4KCi0gSW50ZXJwcmV0YXRpb246IFRoZSBkZW5kcm9ncmFtIHN1cHBvcnRzIHRoZSBjaG9pY2Ugb2YgdHdvIGNsdXN0ZXJzIHNpbmNlIHRoZSBkYXRhIGFwcGVhcnMgdG8gc2VwYXJhdGUgbmF0dXJhbGx5IGludG8gdHdvIG1haW4gZ3JvdXBzLiBUaGlzIGNvbmZpcm1zIHRoZSBvYnNlcnZhdGlvbnMgZnJvbSB0aGUgRWxib3cgYW5kIFNpbGhvdWV0dGUgbWV0aG9kcy4KClBDQSBWaXN1YWxpemF0aW9uIG9mIENsdXN0ZXJzCgoxLiBLLW1lYW5zIENsdXN0ZXJpbmcgKEsgPSAyKToKCi0gVGhlIFBDQSBwbG90IGZvciBrLW1lYW5zIHNob3dzIHRoYXQgdGhlIGRhdGEgaXMgZGl2aWRlZCBpbnRvIHR3byBjbHVzdGVycywgd2l0aCBhIGZhaXJseSBkaXN0aW5jdCBib3VuZGFyeSBiZXR3ZWVuIHRoZW0uCi0gSG93ZXZlciwgdGhlIGF2ZXJhZ2Ugc2lsaG91ZXR0ZSBzY29yZSBmb3Igay1tZWFucyBpcyByZWxhdGl2ZWx5IGxvdyAoMC4yNTU3KSwgc3VnZ2VzdGluZyB0aGF0IHdoaWxlIHRoZSBjbHVzdGVycyBhcmUgc2VwYXJhdGVkLCB0aGV5IG1heSBvdmVybGFwIG9yIGxhY2sgY29oZXNpb24gd2l0aGluIGVhY2ggY2x1c3Rlci4KCjIuIEhpZXJhcmNoaWNhbCBBZ2dsb21lcmF0aXZlIENsdXN0ZXJpbmcgKEhBQykgKEsgPSAyKToKCi0gSW4gdGhlIFBDQSBwbG90IGZvciBIQUMsIG5lYXJseSBhbGwgcG9pbnRzIGFyZSBhc3NpZ25lZCB0byBhIHNpbmdsZSBjbHVzdGVyIChDbHVzdGVyIDEpLCB3aXRoIG9ubHkgYSBmZXcgcG9pbnRzIGFzc2lnbmVkIHRvIENsdXN0ZXIgMi4gVGhpcyByZXN1bHQgY291bGQgaW5kaWNhdGUgdGhhdCBIQUMgKHdpdGggY29tcGxldGUgbGlua2FnZSkgaXMgb3Zlcmx5IGNvbnNlcnZhdGl2ZSBpbiBmb3JtaW5nIHRoZSBzZWNvbmQgY2x1c3Rlci4KLSBEZXNwaXRlIHRoZSB2aXN1YWwgZG9taW5hbmNlIG9mIGEgc2luZ2xlIGNsdXN0ZXIsIHRoZSBzaWxob3VldHRlIHNjb3JlIGZvciBIQUMgaXMgaGlnaGVyICgwLjc3MTkpLCBpbmRpY2F0aW5nIHRoYXQgdGhlIHBvaW50cyB3aXRoaW4gZWFjaCBjbHVzdGVyIGFyZSBtb3JlIGNvaGVzaXZlLCBldmVuIGlmIG9uZSBjbHVzdGVyIGRvbWluYXRlcy4KClN1bW1hcnkgb2YgRmluZGluZ3MKCi0gT3B0aW1hbCBOdW1iZXIgb2YgQ2x1c3RlcnM6IEJvdGggdGhlIEVsYm93IGFuZCBTaWxob3VldHRlIG1ldGhvZHMgc3VnZ2VzdCB0aGF0IDIgY2x1c3RlcnMgYXJlIG9wdGltYWwgZm9yIHRoaXMgZGF0YXNldC4KCi0gay1tZWFucyB2cy4gSEFDOgoKLSBrLW1lYW5zOiBQcm92aWRlcyBhIHJlYXNvbmFibGUgc2VwYXJhdGlvbiBvZiB0aGUgZGF0YSBpbnRvIHR3byBjbHVzdGVycywgYnV0IHRoZSBsb3cgc2lsaG91ZXR0ZSBzY29yZSBzdWdnZXN0cyB0aGF0IHRoZSBjbHVzdGVycyBhcmUgbm90IGFzIHdlbGwtZGVmaW5lZCBvciBjb2hlc2l2ZSBhcyBpbiBIQUMuCgotIEhBQzogQWNoaWV2ZXMgYSBoaWdoZXIgc2lsaG91ZXR0ZSBzY29yZSwgaW5kaWNhdGluZyBiZXR0ZXItZGVmaW5lZCBjbHVzdGVycy4gSG93ZXZlciwgdGhlIFBDQSBwbG90IHNob3dzIGFuIHVuZXZlbiBkaXN0cmlidXRpb24gb2YgcG9pbnRzIGJldHdlZW4gY2x1c3RlcnMsIHdpdGggSEFDIGZvcm1pbmcgb25lIGRvbWluYW50IGNsdXN0ZXIgYW5kIGEgc21hbGxlciBzZWNvbmRhcnkgY2x1c3Rlci4KCkNvbmNsdXNpb246IEJhc2VkIG9uIHNpbGhvdWV0dGUgc2NvcmVzLCBIQUMgaXMgdGhlIGJldHRlciBjaG9pY2UgZm9yIGNsdXN0ZXJpbmcgdGhpcyBkYXRhc2V0IGFzIGl0IGZvcm1zIG1vcmUgY29oZXNpdmUgY2x1c3RlcnMuIEhvd2V2ZXIsIGlmIG1vcmUgYmFsYW5jZWQgY2x1c3RlciBzaXplcyBhcmUgZGVzaXJlZCwgay1tZWFucyB3aXRoIHR3byBjbHVzdGVycyBtaWdodCBiZSBtb3JlIHZpc3VhbGx5IGludGVycHJldGFibGUsIGRlc3BpdGUgaXRzIGxvd2VyIHNpbGhvdWV0dGUgc2NvcmUuCgoKIyMjIGEuIFVzZSBrLW1lYW5zIHRvIGNsdXN0ZXIgdGhlIGRhdGEuIFNob3cgeW91ciB1c2FnZSBvZiBzaWxob3VldHRlIGFuZCB0aGUgZWxib3cgbWV0aG9kIHRvIHBpY2sgdGhlIGJlc3QgbnVtYmVyIG9mIGNsdXN0ZXJzLiBNYWtlIHN1cmUgaXQgaXMgdXNpbmcgbXVsdGlwbGUgcmVzdGFydHMuCgpTdGVwLWJ5LVN0ZXAgUHJvY2VzcyBmb3IgVXNpbmcgSy1tZWFucyBDbHVzdGVyaW5nIHdpdGggRWxib3cgYW5kIFNpbGhvdWV0dGUgTWV0aG9kcwoKU3RlcCAxOiBQcmVwYXJlIHRoZSBEYXRhCgoxLlJlbW92ZSB0aGUgdHlwZSBjb2x1bW4gKGFzIGl0IGNvbnRhaW5zIHRoZSBsYWJlbHMpLgoKMi5TdGFuZGFyZGl6ZSB0aGUgZGF0YSB0byBlbnN1cmUgdGhhdCBhbGwgZmVhdHVyZXMgY29udHJpYnV0ZSBlcXVhbGx5IHRvIHRoZSBkaXN0YW5jZSBjYWxjdWxhdGlvbnMuCgpgYGB7cn0KIyBMb2FkIG5lY2Vzc2FyeSBsaWJyYXJpZXMKbGlicmFyeShjbHVzdGVyKSAgICAgICMgRm9yIHNpbGhvdWV0dGUgYW5hbHlzaXMKbGlicmFyeShmYWN0b2V4dHJhKSAgICMgRm9yIGNsdXN0ZXJpbmcgdmlzdWFsaXphdGlvbiBhbmQgbWV0cmljcwoKIyBSZW1vdmUgJ3R5cGUnIGNvbHVtbiBhbmQgc3RhbmRhcmRpemUgdGhlIGRhdGEKd2luZV9kYXRhX25vX3R5cGUgPC0gd2luZV9kYXRhICU+JSBzZWxlY3QoLXR5cGUpCndpbmVfZGF0YV9zY2FsZWQgPC0gc2NhbGUod2luZV9kYXRhX25vX3R5cGUpCmBgYAoKU3RlcCAyOiBEZXRlcm1pbmUgdGhlIE9wdGltYWwgTnVtYmVyIG9mIENsdXN0ZXJzIFVzaW5nIHRoZSBFbGJvdyBNZXRob2QKCjEuIFJ1biBrLW1lYW5zIGNsdXN0ZXJpbmcgZm9yIGEgcmFuZ2Ugb2YgY2x1c3RlciBudW1iZXJzIChlLmcuLCAyIHRvIDEwKS4KCjIuIENhbGN1bGF0ZSB0aGUgdG90YWwgd2l0aGluLWNsdXN0ZXIgc3VtIG9mIHNxdWFyZXMgKFdTUykgZm9yIGVhY2ggbnVtYmVyIG9mIGNsdXN0ZXJzLgoKMy4gUGxvdCBXU1MgYWdhaW5zdCB0aGUgbnVtYmVyIG9mIGNsdXN0ZXJzIChLKSB0byBpZGVudGlmeSB0aGUgImVsYm93IHBvaW50IiB3aGVyZSBhZGRpbmcgbW9yZSBjbHVzdGVycyBkb2VzbuKAmXQgc2lnbmlmaWNhbnRseSBkZWNyZWFzZSBXU1MuCgpgYGB7cn0KIyBTZXQgYSBzZWVkIGZvciByZXByb2R1Y2liaWxpdHkKc2V0LnNlZWQoMTIzKQoKIyBBcHBseSB0aGUgRWxib3cgTWV0aG9kCndzcyA8LSBzYXBwbHkoMjoxMCwgZnVuY3Rpb24oaykgewogIGttZWFucyh3aW5lX2RhdGFfc2NhbGVkLCBjZW50ZXJzID0gaywgbnN0YXJ0ID0gMTApJHRvdC53aXRoaW5zcwp9KQoKIyBQbG90IHRoZSBFbGJvdyBNZXRob2QgcmVzdWx0cwpwbG90KDI6MTAsIHdzcywgdHlwZSA9ICJiIiwgcGNoID0gMTksIGZyYW1lID0gRkFMU0UsCiAgICAgeGxhYiA9ICJOdW1iZXIgb2YgY2x1c3RlcnMgSyIsCiAgICAgeWxhYiA9ICJUb3RhbCB3aXRoaW4tY2x1c3RlcnMgc3VtIG9mIHNxdWFyZXMiLAogICAgIG1haW4gPSAiRWxib3cgTWV0aG9kIGZvciBPcHRpbWFsIEsiKQpgYGAKU3RlcCAzOiBEZXRlcm1pbmUgdGhlIE9wdGltYWwgTnVtYmVyIG9mIENsdXN0ZXJzIFVzaW5nIHRoZSBTaWxob3VldHRlIE1ldGhvZAoKMS4gUnVuIGstbWVhbnMgY2x1c3RlcmluZyBmb3IgZWFjaCBwb3RlbnRpYWwgbnVtYmVyIG9mIGNsdXN0ZXJzLgoKMi4gQ2FsY3VsYXRlIHRoZSBhdmVyYWdlIHNpbGhvdWV0dGUgc2NvcmUgZm9yIGVhY2ggY29uZmlndXJhdGlvbi4KCjMuIFBsb3QgdGhlIHNpbGhvdWV0dGUgc2NvcmVzIHRvIGlkZW50aWZ5IHRoZSBudW1iZXIgb2YgY2x1c3RlcnMgd2l0aCB0aGUgaGlnaGVzdCBhdmVyYWdlIHNpbGhvdWV0dGUgc2NvcmUuCgpgYGB7cn0KIyBMb2FkIG5lY2Vzc2FyeSBsaWJyYXJpZXMKbGlicmFyeShjbHVzdGVyKSAgICAgICMgRm9yIHNpbGhvdWV0dGUgYW5hbHlzaXMKbGlicmFyeShmYWN0b2V4dHJhKSAgICMgRm9yIGNsdXN0ZXJpbmcgdmlzdWFsaXphdGlvbiBhbmQgbWV0cmljcwpsaWJyYXJ5KGdncGxvdDIpICAgICAgIyBGb3IgcGxvdHRpbmcKCiMgUmVtb3ZlICd0eXBlJyBjb2x1bW4gYW5kIHN0YW5kYXJkaXplIHRoZSBkYXRhCndpbmVfZGF0YV9ub190eXBlIDwtIHdpbmVfZGF0YSAlPiUgc2VsZWN0KC10eXBlKQp3aW5lX2RhdGFfc2NhbGVkIDwtIHNjYWxlKHdpbmVfZGF0YV9ub190eXBlKQoKIyBPcHRpb25hbDogQXBwbHkgUENBIGZvciBkaW1lbnNpb25hbGl0eSByZWR1Y3Rpb24gKGtlZXAgdGhlIGZpcnN0IDUgY29tcG9uZW50cykKcGNhX3Jlc3VsdCA8LSBwcmNvbXAod2luZV9kYXRhX3NjYWxlZCwgY2VudGVyID0gVFJVRSwgc2NhbGUuID0gVFJVRSkKd2luZV9kYXRhX3BjYSA8LSBkYXRhLmZyYW1lKHBjYV9yZXN1bHQkeFssIDE6NV0pICAjIEtlZXAgdGhlIGZpcnN0IDUgY29tcG9uZW50cwoKIyAxLiBFbGJvdyBNZXRob2Qgd2l0aCBpbmNyZWFzZWQgaXRlcmF0aW9ucyBhbmQgbXVsdGlwbGUgcmVzdGFydHMKc2V0LnNlZWQoMTIzKQp3c3MgPC0gc2FwcGx5KDI6MTAsIGZ1bmN0aW9uKGspIHsKICBrbWVhbnMod2luZV9kYXRhX3BjYSwgY2VudGVycyA9IGssIG5zdGFydCA9IDIwLCBpdGVyLm1heCA9IDIwMCkkdG90LndpdGhpbnNzCn0pCgojIFBsb3QgdGhlIEVsYm93IE1ldGhvZCByZXN1bHRzCnBsb3QoMjoxMCwgd3NzLCB0eXBlID0gImIiLCBwY2ggPSAxOSwgZnJhbWUgPSBGQUxTRSwKICAgICB4bGFiID0gIk51bWJlciBvZiBjbHVzdGVycyBLIiwKICAgICB5bGFiID0gIlRvdGFsIHdpdGhpbi1jbHVzdGVycyBzdW0gb2Ygc3F1YXJlcyIsCiAgICAgbWFpbiA9ICJFbGJvdyBNZXRob2QgZm9yIE9wdGltYWwgSyIpCgojIDIuIFNpbGhvdWV0dGUgTWV0aG9kIHdpdGggaW5jcmVhc2VkIGl0ZXJhdGlvbnMgYW5kIFBDQS10cmFuc2Zvcm1lZCBkYXRhCnNpbF93aWR0aCA8LSBzYXBwbHkoMjoxMCwgZnVuY3Rpb24oaykgewogIGttX3JlcyA8LSBrbWVhbnMod2luZV9kYXRhX3BjYSwgY2VudGVycyA9IGssIG5zdGFydCA9IDIwLCBpdGVyLm1heCA9IDIwMCkKICBzcyA8LSBzaWxob3VldHRlKGttX3JlcyRjbHVzdGVyLCBkaXN0KHdpbmVfZGF0YV9wY2EpKQogIG1lYW4oc3NbLCAzXSkgICMgQXZlcmFnZSBzaWxob3VldHRlIHdpZHRoCn0pCgojIFBsb3QgdGhlIFNpbGhvdWV0dGUgTWV0aG9kIHJlc3VsdHMKcGxvdCgyOjEwLCBzaWxfd2lkdGgsIHR5cGUgPSAiYiIsIHBjaCA9IDE5LCBmcmFtZSA9IEZBTFNFLAogICAgIHhsYWIgPSAiTnVtYmVyIG9mIGNsdXN0ZXJzIEsiLAogICAgIHlsYWIgPSAiQXZlcmFnZSBTaWxob3VldHRlIFdpZHRoIiwKICAgICBtYWluID0gIlNpbGhvdWV0dGUgTWV0aG9kIGZvciBPcHRpbWFsIEsiKQphYmxpbmUoaCA9IG1heChzaWxfd2lkdGgpLCBjb2wgPSAicmVkIiwgbHR5ID0gMikKYGBgCgoKU3RlcCA0OiBQZXJmb3JtIEZpbmFsIGstbWVhbnMgQ2x1c3RlcmluZyB3aXRoIHRoZSBDaG9zZW4gSwoKQmFzZWQgb24gdGhlIGVsYm93IGFuZCBzaWxob3VldHRlIHBsb3RzLCBzZWxlY3QgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzIChlLmcuLCAyKS4gVGhlbiwgcGVyZm9ybSBrLW1lYW5zIGNsdXN0ZXJpbmcgd2l0aCB0aGlzIEsgdmFsdWUuCmBgYHtyfQojIENob29zZSB0aGUgb3B0aW1hbCBLIGJhc2VkIG9uIHRoZSBwbG90cyAod2UgY29uZmlybWVkIEsgPSAyKQpvcHRpbWFsX2sgPC0gMgoKIyBQZXJmb3JtIGZpbmFsIGstbWVhbnMgY2x1c3RlcmluZyB3aXRoIGluY3JlYXNlZCBuc3RhcnQgYW5kIGl0ZXIubWF4CmttZWFuc19yZXN1bHQgPC0ga21lYW5zKHdpbmVfZGF0YV9zY2FsZWQsIGNlbnRlcnMgPSBvcHRpbWFsX2ssIG5zdGFydCA9IDIwLCBpdGVyLm1heCA9IDIwMCkKCiMgUHJlcGFyZSBkYXRhIGZvciBQQ0EgdmlzdWFsaXphdGlvbiAodXNpbmcgdGhlIG9yaWdpbmFsIFBDQSByZXN1bHQgaWYgYXZhaWxhYmxlKQpwY2FfZGF0YV9jbHVzdGVycyA8LSBkYXRhLmZyYW1lKFBDMSA9IHBjYV9yZXN1bHQkeFssIDFdLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFBDMiA9IHBjYV9yZXN1bHQkeFssIDJdLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGttZWFuc19jbHVzdGVyID0gYXMuZmFjdG9yKGttZWFuc19yZXN1bHQkY2x1c3RlcikpCgojIFZpc3VhbGl6ZSB0aGUgY2x1c3RlcmluZyByZXN1bHRzIGluIFBDQSBzcGFjZQpnZ3Bsb3QocGNhX2RhdGFfY2x1c3RlcnMsIGFlcyh4ID0gUEMxLCB5ID0gUEMyLCBjb2xvciA9IGttZWFuc19jbHVzdGVyKSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjcpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoIlBDQSBvZiBXaW5lIERhdGEgd2l0aCBLLW1lYW5zIENsdXN0ZXJzIChrID0iLCBvcHRpbWFsX2ssICIpIiksCiAgICAgICBjb2xvciA9ICJLLW1lYW5zIENsdXN0ZXIiKSArCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKSW50ZXJwcmV0YXRpb24gb2YgdGhlIFBDQSBQbG90IHdpdGggay1tZWFucyBDbHVzdGVycyAoSyA9IDIpCgoxLiBDbHVzdGVyIFNlcGFyYXRpb246CgotIFRoZSBwbG90IHNob3dzIHR3byBkaXN0aW5jdCBjbHVzdGVycywgbGFiZWxlZCBhcyBDbHVzdGVyIDEgKHJlZCkgYW5kIENsdXN0ZXIgMiAoYmx1ZSkuCgotIFRoZSBjbHVzdGVycyBhcmUgd2VsbC1zZXBhcmF0ZWQgaW4gdGhlIFBDQSBzcGFjZSwgaW5kaWNhdGluZyB0aGF0IGstbWVhbnMgd2FzIGFibGUgdG8gZWZmZWN0aXZlbHkgZGlmZmVyZW50aWF0ZSB0d28gbWFpbiBncm91cHMgd2l0aGluIHRoZSBkYXRhLiBUaGlzIGFsaWducyB3aXRoIHRoZSByZXN1bHRzIGZyb20gdGhlIHNpbGhvdWV0dGUgYW5kIGVsYm93IG1ldGhvZHMgdGhhdCBzdWdnZXN0ZWQgSyA9IDIgYXMgb3B0aW1hbC4KCjIuSW50ZXJwcmV0YXRpb24gb2YgdGhlIFBDQSBBeGVzOgoKLSBQQzEgYW5kIFBDMiByZXByZXNlbnQgdGhlIHByaW5jaXBhbCBjb21wb25lbnRzIHRoYXQgY2FwdHVyZSB0aGUgbWF4aW11bSB2YXJpYW5jZSBpbiB0aGUgZGF0YS4KCi0gVGhlIHNlcGFyYXRpb24gYWxvbmcgUEMxIChob3Jpem9udGFsIGF4aXMpIGFwcGVhcnMgdG8gYmUgdGhlIHByaW1hcnkgZHJpdmVyIGluIGRpc3Rpbmd1aXNoaW5nIHRoZSBjbHVzdGVycy4gVGhpcyBzdWdnZXN0cyB0aGF0IHRoZSBtYWluIGRpZmZlcmVuY2VzIGJldHdlZW4gdGhlIGNsdXN0ZXJzIGFyZSBhbG9uZyB0aGlzIGNvbXBvbmVudCwgcG9zc2libHkgcmVmbGVjdGluZyB2YXJpYXRpb25zIGluIGNlcnRhaW4gd2luZSBxdWFsaXR5IGF0dHJpYnV0ZXMuCgozLiBDbHVzdGVyIENvaGVzaW9uOgoKLSBUaGUgY2x1c3RlcnMgYXBwZWFyIGZhaXJseSBjb2hlc2l2ZSwgd2l0aCBsaW1pdGVkIG92ZXJsYXAgYmV0d2VlbiB0aGVtIGluIHRoZSBQQ0EgcHJvamVjdGlvbi4gVGhpcyBzdWdnZXN0cyB0aGF0IHRoZSBjbHVzdGVycyBhcmUgd2VsbC1kZWZpbmVkIGluIHRoZSBQQ0Egc3BhY2UuCi0gVGhlIHNpbGhvdWV0dGUgc2NvcmUgd2FzIGFyb3VuZCAwLjMwLCB3aGljaCBpcyBub3QgcGFydGljdWxhcmx5IGhpZ2gsIGluZGljYXRpbmcgbW9kZXJhdGUgY29oZXNpb24gd2l0aGluIGVhY2ggY2x1c3Rlci4gSG93ZXZlciwgaW4gUENBIHNwYWNlLCB0aGUgc2VwYXJhdGlvbiBsb29rcyB2aXN1YWxseSBjbGVhci4KCjQuIFByYWN0aWNhbCBJbnRlcnByZXRhdGlvbjoKCi0gR2l2ZW4gdGhhdCB0aGUgZGF0YXNldCBpbmNsdWRlcyBkaWZmZXJlbnQgd2luZSBxdWFsaXR5IGF0dHJpYnV0ZXMsIHRoZXNlIGNsdXN0ZXJzIG1heSByZXByZXNlbnQgZGlmZmVyZW50IHR5cGVzIG9yIHF1YWxpdGllcyBvZiB3aW5lcyAoZS5nLiwgcG90ZW50aWFsbHkgY2x1c3RlcmluZyBiYXNlZCBvbiBjaGVtaWNhbCBjb21wb3NpdGlvbnMgb3IgcXVhbGl0eSByYXRpbmdzKS4KLSBXaXRob3V0IHRoZSB0eXBlIGxhYmVsIChyZWQgb3Igd2hpdGUpLCB0aGlzIGNsdXN0ZXJpbmcgaXMgcHVyZWx5IGRhdGEtZHJpdmVuLCBzbyBmdXJ0aGVyIGFuYWx5c2lzIGNvdWxkIGJlIGRvbmUgdG8gaW50ZXJwcmV0IHdoYXQgc3BlY2lmaWMgYXR0cmlidXRlcyBhcmUgZHJpdmluZyB0aGlzIHNlcGFyYXRpb24uCgojIyMgYi4gVXNlIGhpZXJhcmNoaWNhbCBhZ2dsb21lcmF0aXZlIGNsdXN0ZXJpbmcgKEhBQykgdG8gY2x1c3RlciB0aGUgZGF0YS4gVHJ5IGF0IGxlYXN0IDIgZGlzdGFuY2UgZnVuY3Rpb25zIGFuZCBhdCBsZWFzdCAyIGxpbmthZ2UgZnVuY3Rpb25zIChjbHVzdGVyIGRpc3RhbmNlIGZ1bmN0aW9ucyksIGZvciBhIHRvdGFsIG9mIDQgcGFyYW1ldGVyIGNvbWJpbmF0aW9ucy4gRm9yIGVhY2ggcGFyYW1ldGVyIGNvbWJpbmF0aW9uLCBwZXJmb3JtIHRoZSBjbHVzdGVyaW5nLgoKU3RlcC1ieS1TdGVwIENvZGUgZm9yIEhBQyB3aXRoIERpZmZlcmVudCBQYXJhbWV0ZXJzCgpTdGVwIDE6IExvYWQgTmVjZXNzYXJ5IExpYnJhcmllcwoKRW5zdXJlIHRoYXQgdGhlIHJlcXVpcmVkIHBhY2thZ2VzIGFyZSBsb2FkZWQuCgpgYGB7cn0KIyBMb2FkIHJlcXVpcmVkIHBhY2thZ2VzCmxpYnJhcnkoY2x1c3RlcikgICAgICAjIEZvciBjbHVzdGVyaW5nIGZ1bmN0aW9ucyBhbmQgZGlzdGFuY2UgY2FsY3VsYXRpb25zCmxpYnJhcnkoZmFjdG9leHRyYSkgICAjIEZvciB2aXN1YWxpemluZyBkZW5kcm9ncmFtcwpsaWJyYXJ5KGRlbmRleHRlbmQpICAgIyBGb3IgZGVuZHJvZ3JhbSBtYW5pcHVsYXRpb24gYW5kIGN1dHRpbmcKYGBgCgpgYGB7cn0KIyBDaGVjayBmb3IgbWlzc2luZyB2YWx1ZXMgaW4gZWFjaCBjb2x1bW4KY29sU3Vtcyhpcy5uYSh3aW5lX2RhdGEpKQoKIyBBbHRlcm5hdGl2ZWx5LCB0byBnZXQgYSBxdWljayBzdW1tYXJ5OgpzdW1tYXJ5KHdpbmVfZGF0YSkKCiMgSWYgeW91IHdhbnQgdG8ga25vdyBpZiB0aGVyZSBhcmUgYW55IG1pc3NpbmcgdmFsdWVzIGluIHRoZSBlbnRpcmUgZGF0YXNldDoKYW55KGlzLm5hKHdpbmVfZGF0YSkpCmBgYAoKU3RlcCAyOiBEZWZpbmUgRGlzdGFuY2UgYW5kIExpbmthZ2UgQ29tYmluYXRpb25zCgpXZSB3aWxsIHRyeToKCi0gRGlzdGFuY2UgZnVuY3Rpb25zOiBFdWNsaWRlYW4gYW5kIE1hbmhhdHRhbgotTGlua2FnZSBmdW5jdGlvbnM6IENvbXBsZXRlIGFuZCBBdmVyYWdlCmBgYHtyfQojIENoZWNrIGZvciBudWxsIHZhbHVlcyBpbiBlYWNoIGNvbHVtbgpjb2xTdW1zKGlzLm5hKHdpbmVfZGF0YSkpCgojIEFsdGVybmF0aXZlbHksIGEgc3VtbWFyeSB3aXRoIE5BIGNvdW50cyBpbmNsdWRlZApzdW1tYXJ5KHdpbmVfZGF0YSkKYGBgCgoKYGBge3J9CiMgTG9hZCByZXF1aXJlZCBsaWJyYXJpZXMKbGlicmFyeShjbHVzdGVyKQpsaWJyYXJ5KGZhY3RvZXh0cmEpCgojIFN0ZXAgMTogUmVtb3ZlIHRoZSAndHlwZScgY29sdW1uIGFuZCBzY2FsZSB0aGUgZGF0YQp3aW5lX2RhdGFfbnVtZXJpYyA8LSB3aW5lX2RhdGFbLCBzYXBwbHkod2luZV9kYXRhLCBpcy5udW1lcmljKV0Kd2luZV9kYXRhX3NjYWxlZCA8LSBzY2FsZSh3aW5lX2RhdGFfbnVtZXJpYykKCiMgU3RlcCAyOiBEZWZpbmUgZGlzdGFuY2UgYW5kIGxpbmthZ2UgbWV0aG9kcwpkaXN0YW5jZV9tZXRob2RzIDwtIGxpc3QoCiAgZXVjbGlkZWFuID0gZGlzdCh3aW5lX2RhdGFfc2NhbGVkLCBtZXRob2QgPSAiZXVjbGlkZWFuIiksCiAgbWFuaGF0dGFuID0gZGlzdCh3aW5lX2RhdGFfc2NhbGVkLCBtZXRob2QgPSAibWFuaGF0dGFuIikKKQpsaW5rYWdlX21ldGhvZHMgPC0gYygic2luZ2xlIiwgImNvbXBsZXRlIikKCiMgU3RlcCAzOiBQZXJmb3JtIGNsdXN0ZXJpbmcgd2l0aG91dCB2aXN1YWxpemluZyBsYXJnZSBkZW5kcm9ncmFtcwpmb3IgKGRpc3RfbmFtZSBpbiBuYW1lcyhkaXN0YW5jZV9tZXRob2RzKSkgewogIGZvciAobGlua2FnZSBpbiBsaW5rYWdlX21ldGhvZHMpIHsKICAgIGNhdCgiUHJvY2Vzc2luZzoiLCBkaXN0X25hbWUsICJkaXN0YW5jZSB3aXRoIiwgbGlua2FnZSwgImxpbmthZ2UuLi5cbiIpCiAgICBoYyA8LSBoY2x1c3QoZGlzdGFuY2VfbWV0aG9kc1tbZGlzdF9uYW1lXV0sIG1ldGhvZCA9IGxpbmthZ2UpCiAgICAKICAgICMgVXNlIGN1dHJlZSB0byBnZXQgY2x1c3RlcnMgd2l0aG91dCB2aXN1YWxpemluZwogICAgY2x1c3Rlcl9hc3NpZ25tZW50cyA8LSBjdXRyZWUoaGMsIGsgPSAzKSAgIyBBZGp1c3QgayBhcyBuZWVkZWQgZm9yIG51bWJlciBvZiBjbHVzdGVycwogICAgcHJpbnQodGFibGUoY2x1c3Rlcl9hc3NpZ25tZW50cykpICAjIFNob3cgY2x1c3RlciBzaXplcyBmb3IgY29uZmlybWF0aW9uCiAgICAKICAgIHJtKGhjLCBjbHVzdGVyX2Fzc2lnbm1lbnRzKSAgIyBGcmVlIHVwIG1lbW9yeQogICAgZ2MoKSAgIyBHYXJiYWdlIGNvbGxlY3Rpb24KICB9Cn0KYGBgCgoKIyMjIGMuIENvbXBhcmUgdGhlIGstbWVhbnMgYW5kIEhBQyBjbHVzdGVyaW5ncyBieSBjcmVhdGluZyBhIGNyb3NzdGFidWxhdGlvbiBiZXR3ZWVuIHRoZWlyIGxhYmVscy4KCmBgYHtyfQojIExvYWQgbmVjZXNzYXJ5IGxpYnJhcmllcwpsaWJyYXJ5KGNsdXN0ZXIpCmxpYnJhcnkoZmFjdG9leHRyYSkKCiMgU3RlcCAxOiBQZXJmb3JtIGstbWVhbnMgY2x1c3RlcmluZwpzZXQuc2VlZCgxMjMpICAjIEZvciByZXByb2R1Y2liaWxpdHkKa21lYW5zX3Jlc3VsdCA8LSBrbWVhbnMod2luZV9kYXRhX3NjYWxlZCwgY2VudGVycyA9IDMpCmttZWFuc19sYWJlbHMgPC0ga21lYW5zX3Jlc3VsdCRjbHVzdGVyCgojIFN0ZXAgMjogUGVyZm9ybSBIQUMgY2x1c3RlcmluZwojIFVzaW5nIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHdpdGggY29tcGxldGUgbGlua2FnZSBhbmQgRXVjbGlkZWFuIGRpc3RhbmNlCmhjIDwtIGhjbHVzdChkaXN0KHdpbmVfZGF0YV9zY2FsZWQsIG1ldGhvZCA9ICJldWNsaWRlYW4iKSwgbWV0aG9kID0gImNvbXBsZXRlIikKaGFjX2xhYmVscyA8LSBjdXRyZWUoaGMsIGsgPSAzKSAgIyBDdXQgdGhlIHRyZWUgdG8gZm9ybSAzIGNsdXN0ZXJzCgojIFN0ZXAgMzogQ3JlYXRlIGEgY3Jvc3N0YWJ1bGF0aW9uIGJldHdlZW4gay1tZWFucyBhbmQgSEFDIGxhYmVscwpjcm9zc3RhYiA8LSB0YWJsZShrbWVhbnNfbGFiZWxzLCBoYWNfbGFiZWxzKQpwcmludChjcm9zc3RhYikKCmBgYAoKSW50ZXJwcmV0YXRpb246CgotIENsdXN0ZXIgT3ZlcmxhcDogVGhlIHRhYmxlIGluZGljYXRlcyB0aGF0IHRoZSBtYWpvcml0eSBvZiBrLW1lYW5zIGNsdXN0ZXJzIGFsaWduIGhlYXZpbHkgd2l0aCBIQUMgY2x1c3RlciAxLgoKICAtIGstbWVhbnMgQ2x1c3RlciAxOiBDb250YWlucyAyOTA4IGRhdGEgcG9pbnRzLCBhbGwgYXNzaWduZWQgdG8gSEFDIGNsdXN0ZXIgMS4KICAtIGstbWVhbnMgQ2x1c3RlciAyOiBJbmNsdWRlcyAxNjE3IGRhdGEgcG9pbnRzIG1vc3RseSBpbiBIQUMgY2x1c3RlciAxLCB3aXRoIGEgdmVyeSBzbWFsbCBzcGlsbG92ZXIgKDIgcG9pbnRzKSBpbnRvIEhBQyBjbHVzdGVyIDIuCiAgLSBrLW1lYW5zIENsdXN0ZXIgMzogQ29udGFpbnMgMTk2OSBkYXRhIHBvaW50cyBpbiBIQUMgY2x1c3RlciAxLCB3aXRoIG9ubHkgMSBkYXRhIHBvaW50IGluIEhBQyBjbHVzdGVyIDMuCgotIERpc3RpbmN0IENsdXN0ZXJzOiBUaGUgY2x1c3RlcmluZyBhc3NpZ25tZW50IHNob3dzIHRoYXQgYWxtb3N0IGFsbCBwb2ludHMgYWNyb3NzIGstbWVhbnMgY2x1c3RlcnMgYXJlIGFsbG9jYXRlZCB0byBIQUMgY2x1c3RlciAxLCB3aXRoIHZlcnkgZmV3IHBvaW50cyBpbiBIQUMgY2x1c3RlcnMgMiBhbmQgMy4KCkFuYWx5c2lzOgoKLSBIaWdoIENvbnNpc3RlbmN5OiBUaGVyZSBpcyBhIHN0cm9uZyBkZWdyZWUgb2YgY29uc2lzdGVuY3kgYmV0d2VlbiBrLW1lYW5zIGFuZCBIQUMgY2x1c3RlcmluZyBhc3NpZ25tZW50cywgYXMgZXZpZGVuY2VkIGJ5IHRoZSBsYXJnZSBvdmVybGFwIHdpdGggSEFDIGNsdXN0ZXIgMS4gVGhpcyBzdWdnZXN0cyB0aGF0IGJvdGggbWV0aG9kcyByZWNvZ25pemUgYSBkb21pbmFudCB1bmRlcmx5aW5nIGNsdXN0ZXIgc3RydWN0dXJlIHdpdGhpbiB0aGUgZGF0YXNldC4KCi0gTWluaW1hbCBDbHVzdGVyIFZhcmlhdGlvbjogT25seSBhIGZldyBwb2ludHMgc2hvdyBkaWZmZXJpbmcgYXNzaWdubWVudHMgaW4gSEFDIGNsdXN0ZXJzIDIgYW5kIDMsIHBhcnRpY3VsYXJseSBmcm9tIGstbWVhbnMgY2x1c3RlcnMgMiBhbmQgMy4gVGhlc2Ugc21hbGwgdmFyaWF0aW9ucyBtYXkgcmVmbGVjdCBkaWZmZXJlbmNlcyBpbiBob3cgZWFjaCBhbGdvcml0aG0gdHJlYXRzIGRpc3RhbmNlcyBhbmQgZGVmaW5lcyBjbHVzdGVycywgZXNwZWNpYWxseSB3aXRoIEhBQ+KAmXMgbGlua2FnZSBtZXRob2QgYW5kIGstbWVhbnMgY2VudHJvaWQtYmFzZWQgYXBwcm9hY2guCgpDb25jbHVzaW9uOgoKQm90aCBjbHVzdGVyaW5nIG1ldGhvZHMgY2FwdHVyZSBhIHNpbWlsYXIgc3RydWN0dXJlIGluIHRoZSBkYXRhLCB3aXRoIG9uZSBsYXJnZSwgZG9taW5hbnQgY2x1c3RlciBhbmQgbWluaW1hbCB2YXJpYWJpbGl0eSBpbiBjbHVzdGVyaW5nIGFzc2lnbm1lbnRzIGFjcm9zcyBvdGhlciBjbHVzdGVycy4gTWlub3IgZGlzY3JlcGFuY2llcyBhcmUgbGlrZWx5IGR1ZSB0byB0aGUgZGlmZmVyaW5nIGRpc3RhbmNlIG1lYXN1cmVzIGFuZCBhcHByb2FjaGVzIHRvIGNsdXN0ZXIgZm9ybWF0aW9uIHVzZWQgYnkgSEFDIGFuZCBrLW1lYW5zLiBUaGlzIHN0cm9uZyBhbGlnbm1lbnQgaGlnaGxpZ2h0cyB0aGF0IHRoZSBkYXRhIGxpa2VseSBoYXMgb25lIG1haW4gY2x1c3RlciB3aXRoIHNvbWUgbWlub3IsIGxlc3MgZGlzdGluY3Qgc3ViZ3JvdXBpbmdzLgoKCgojIyMgZC4gRm9yIGNvbXBhcmlzb24g4oCTIHVzZSBQQ0EgdG8gdmlzdWFsaXplIHRoZSBkYXRhIGluIGEgc2NhdHRlcnBsb3QuIENyZWF0ZSAzIHNlcGFyYXRlIHBsb3RzOiB1c2UgdGhlIGNvbG9yIG9mIHRoZSBwb2ludHMgdG8gc2hvdyAoMSkgdGhlIHR5cGUgbGFiZWwsICgyKSB0aGUgay1tZWFucyBjbHVzdGVyIGxhYmVscyBhbmQgKDMpIHRoZSBIQUMgY2x1c3RlciBsYWJlbHMuCgpgYGB7cn0KIyBMb2FkIG5lY2Vzc2FyeSBsaWJyYXJpZXMKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGZhY3RvZXh0cmEpCgojIFN0ZXAgMTogU2NhbGUgdGhlIGRhdGEgYW5kIHBlcmZvcm0gUENBCndpbmVfZGF0YV9zY2FsZWQgPC0gc2NhbGUod2luZV9kYXRhX251bWVyaWMpCnBjYV9yZXN1bHQgPC0gcHJjb21wKHdpbmVfZGF0YV9zY2FsZWQpCgojIEV4dHJhY3QgdGhlIGZpcnN0IHR3byBwcmluY2lwYWwgY29tcG9uZW50cyBmb3IgcGxvdHRpbmcKcGNhX2RhdGEgPC0gYXMuZGF0YS5mcmFtZShwY2FfcmVzdWx0JHhbLCAxOjJdKSAgIyBQQzEgYW5kIFBDMgpjb2xuYW1lcyhwY2FfZGF0YSkgPC0gYygiUEMxIiwgIlBDMiIpCgojIFN0ZXAgMjogQWRkIHR5cGUsIGstbWVhbnMsIGFuZCBIQUMgbGFiZWxzIHRvIHRoZSBQQ0EgZGF0YQpwY2FfZGF0YSR0eXBlIDwtIHdpbmVfZGF0YSR0eXBlICAjIE9yaWdpbmFsIHR5cGUgbGFiZWwKcGNhX2RhdGEka21lYW5zX2xhYmVscyA8LSBmYWN0b3Ioa21lYW5zX3Jlc3VsdCRjbHVzdGVyKSAgIyBLLW1lYW5zIGNsdXN0ZXIgbGFiZWxzCnBjYV9kYXRhJGhhY19sYWJlbHMgPC0gZmFjdG9yKGhhY19sYWJlbHMpICAjIEhBQyBjbHVzdGVyIGxhYmVscwoKIyBTdGVwIDM6IFBsb3QgdGhlIFBDQSB3aXRoIGRpZmZlcmVudCBjb2xvciBsYWJlbHMKCiMgKDEpIFBDQSBwbG90IGNvbG9yZWQgYnkgdHlwZSBsYWJlbApnZ3Bsb3QocGNhX2RhdGEsIGFlcyh4ID0gUEMxLCB5ID0gUEMyLCBjb2xvciA9IHR5cGUpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuNykgKwogIGxhYnModGl0bGUgPSAiUENBIFBsb3QgQ29sb3JlZCBieSBUeXBlIExhYmVsIikgKwogIHRoZW1lX21pbmltYWwoKQoKIyAoMikgUENBIHBsb3QgY29sb3JlZCBieSBrLW1lYW5zIGNsdXN0ZXIgbGFiZWxzCmdncGxvdChwY2FfZGF0YSwgYWVzKHggPSBQQzEsIHkgPSBQQzIsIGNvbG9yID0ga21lYW5zX2xhYmVscykpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC43KSArCiAgbGFicyh0aXRsZSA9ICJQQ0EgUGxvdCBDb2xvcmVkIGJ5IEstbWVhbnMgQ2x1c3RlciBMYWJlbHMiKSArCiAgdGhlbWVfbWluaW1hbCgpCgojICgzKSBQQ0EgcGxvdCBjb2xvcmVkIGJ5IEhBQyBjbHVzdGVyIGxhYmVscwpnZ3Bsb3QocGNhX2RhdGEsIGFlcyh4ID0gUEMxLCB5ID0gUEMyLCBjb2xvciA9IGhhY19sYWJlbHMpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuNykgKwogIGxhYnModGl0bGUgPSAiUENBIFBsb3QgQ29sb3JlZCBieSBIQUMgQ2x1c3RlciBMYWJlbHMiKSArCiAgdGhlbWVfbWluaW1hbCgpCmBgYApFeHBsYW5hdGlvbiBvZiB0aGUgQ29kZToKCi0gUENBIENhbGN1bGF0aW9uOiBQQ0EgcmVkdWNlcyB0aGUgZGF0YXNldCB0byBpdHMgZmlyc3QgdHdvIHByaW5jaXBhbCBjb21wb25lbnRzIChQQzEgYW5kIFBDMiksIGNhcHR1cmluZyBtb3N0IG9mIHRoZSBkYXRh4oCZcyB2YXJpYW5jZS4KCi0gU2NhdHRlcnBsb3RzOgoKICAtIFBsb3QgMTogUG9pbnRzIGFyZSBjb2xvcmVkIGJ5IHRoZSBvcmlnaW5hbCB3aW5lIHR5cGUgbGFiZWwuCiAgCiAgLSBQbG90IDI6IFBvaW50cyBhcmUgY29sb3JlZCBiYXNlZCBvbiBrLW1lYW5zIGNsdXN0ZXIgYXNzaWdubWVudHMuCgogIC0gUGxvdCAzOiBQb2ludHMgYXJlIGNvbG9yZWQgYWNjb3JkaW5nIHRvIHRoZSBIQUMgY2x1c3RlciBsYWJlbHMuCiAgCgojIyMgZS4gQ29uc2lkZXIgdGhlIHJlc3VsdHMgb2YgQyBhbmQgRCBhbmQgZXhwbGFpbiB0aGUgZGlmZmVyZW5jZXMgYmV0d2VlbiB0aGUgY2x1c3RlcmluZyByZXN1bHRzIGluIHRlcm1zIG9mIGhvdyB0aGUgYWxnb3JpdGhtcyB3b3JrLgoKQW5zd2VyczoKClRoZSBkaWZmZXJlbmNlcyBpbiBjbHVzdGVyaW5nIHJlc3VsdHMgYmV0d2VlbiBLLW1lYW5zIGFuZCBIaWVyYXJjaGljYWwgQWdnbG9tZXJhdGl2ZSBDbHVzdGVyaW5nIChIQUMpIGNhbiBiZSBhdHRyaWJ1dGVkIHRvIGhvdyBlYWNoIGFsZ29yaXRobSBkZWZpbmVzIGFuZCBmb3JtcyBjbHVzdGVycy4gSGVyZeKAmXMgYSBicmVha2Rvd24gYmFzZWQgb24gdGhlIG9ic2VydmF0aW9ucyBmcm9tIHBhcnRzIEMgYW5kIEQ6CgoxLiBLLW1lYW5zIENsdXN0ZXJpbmc6CgotIE1lY2hhbmlzbTogSy1tZWFucyBhaW1zIHRvIHBhcnRpdGlvbiB0aGUgZGF0YXNldCBpbnRvIGEgcHJlZGV0ZXJtaW5lZCBudW1iZXIgb2YgY2x1c3RlcnMgYnkgaXRlcmF0aXZlbHkgbWluaW1pemluZyB0aGUgdmFyaWFuY2Ugd2l0aGluIGVhY2ggY2x1c3Rlci4gSXQgZG9lcyB0aGlzIGJ5IGFzc2lnbmluZyBwb2ludHMgdG8gdGhlIG5lYXJlc3QgY2x1c3RlciBjZW50cm9pZCBhbmQgYWRqdXN0aW5nIGNlbnRyb2lkcyBiYXNlZCBvbiB0aGUgbWVhbiBwb3NpdGlvbiBvZiB0aGUgcG9pbnRzIHdpdGhpbiBlYWNoIGNsdXN0ZXIuCgotIFJlc3VsdHMgaW4gUGFydCBDOiBLLW1lYW5zIGZvcm1lZCB0aHJlZSBjbHVzdGVycyB3aXRoIHNpZ25pZmljYW50IG92ZXJsYXAgaW4gSEFDIGNsdXN0ZXIgMSwgaW5kaWNhdGluZyB0aGF0IEstbWVhbnMgZGV0ZWN0ZWQgb25lIGRvbWluYW50IGNsdXN0ZXIgc3RydWN0dXJlIGJ1dCBhbHNvIHNlcGFyYXRlZCB0aGUgZGF0YSBpbnRvIHNtYWxsZXIsIGNvbXBhY3QgY2x1c3RlcnMgdG8gbWF0Y2ggdGhlIHNwZWNpZmllZCBudW1iZXIgb2YgY2x1c3RlcnMgKHRocmVlIGluIHRoaXMgY2FzZSkuCgotIEVmZmVjdCBvZiBDZW50cm9pZC1CYXNlZCBDbHVzdGVyaW5nOiBUaGUgY2VudHJvaWQtYmFzZWQgYXBwcm9hY2ggZm9yY2VzIGNsdXN0ZXJzIHRvIGJlIG9mIHJlbGF0aXZlbHkgc2ltaWxhciBzaXplIGFuZCBzaGFwZSAoc3BoZXJpY2FsKS4gVGhpcyBhcHByb2FjaCB3b3JrcyB3ZWxsIHdoZW4gdGhlIGRhdGEgbmF0dXJhbGx5IGZvcm1zIGRlbnNlLCBjb21wYWN0IGdyb3VwcywgYXMgaXQgdHJpZXMgdG8gZXZlbmx5IHBhcnRpdGlvbiB0aGUgZGF0YSBwb2ludHMgYXJvdW5kIGNlbnRyb2lkcy4gSW4gdGhpcyBjYXNlLCBLLW1lYW5zIHJlY29nbml6ZWQgc3ViZ3JvdXBzIHdpdGhpbiB0aGUgbGFyZ2UgSEFDIGNsdXN0ZXIgYnV0IGNvdWxkbuKAmXQgY2FwdHVyZSBzbWFsbGVyIHZhcmlhdGlvbnMgYXMgZGlzdGluY3QgY2x1c3RlcnMuCgoyLiBIaWVyYXJjaGljYWwgQWdnbG9tZXJhdGl2ZSBDbHVzdGVyaW5nIChIQUMpOgoKLSBNZWNoYW5pc206IEhBQyBzdGFydHMgYnkgdHJlYXRpbmcgZWFjaCBkYXRhIHBvaW50IGFzIGl0cyBvd24gY2x1c3RlciBhbmQgdGhlbiBpdGVyYXRpdmVseSBtZXJnZXMgdGhlIGNsb3Nlc3QgY2x1c3RlcnMgYmFzZWQgb24gYSBzcGVjaWZpZWQgbGlua2FnZSBjcml0ZXJpb24gKGUuZy4sIGNvbXBsZXRlIGxpbmthZ2UgdXNlZCBoZXJlKS4gVGhpcyBtZXJnaW5nIGNvbnRpbnVlcyB1bnRpbCBvbmx5IG9uZSBjbHVzdGVyIHJlbWFpbnMsIGNyZWF0aW5nIGEgaGllcmFyY2h5IG9mIGNsdXN0ZXJzIChkZW5kcm9ncmFtKS4KCi0gUmVzdWx0cyBpbiBQYXJ0IEM6IEhBQyBncm91cGVkIG1vc3Qgb2YgdGhlIGRhdGEgaW50byBvbmUgZG9taW5hbnQgY2x1c3RlciAoY2x1c3RlciAxKSBhbmQgaWRlbnRpZmllZCBvbmx5IGEgZmV3IHBvaW50cyBhcyBzZXBhcmF0ZSBjbHVzdGVycyAoY2x1c3RlcnMgMiBhbmQgMykuIFRoaXMgb3V0Y29tZSBzaG93cyB0aGF0IEhBQywgcGFydGljdWxhcmx5IHdpdGggY29tcGxldGUgbGlua2FnZSwgZW1waGFzaXplcyBjb2hlc2l2ZSBjbHVzdGVycyBieSBmb2N1c2luZyBvbiBmYXJ0aGVzdCBkaXN0YW5jZXMgd2hlbiBtZXJnaW5nLgoKLSBFZmZlY3Qgb2YgRGlzdGFuY2UtQmFzZWQgSGllcmFyY2hpY2FsIENsdXN0ZXJpbmc6IEhBQ+KAmXMgYXBwcm9hY2ggYWxsb3dzIGZvciBjYXB0dXJpbmcgc21hbGwsIGRpc3RhbnQgY2x1c3RlcnMgYXMgc2VwYXJhdGUgZ3JvdXBzLiBIb3dldmVyLCBpdOKAmXMgbGVzcyBjb25zdHJhaW5lZCBieSBzaXplLCBtZWFuaW5nIGl0IGNhbiBjcmVhdGUgaW1iYWxhbmNlZCBjbHVzdGVycy4gSW4gdGhpcyBkYXRhc2V0LCBIQUMgZGV0ZWN0ZWQgb25lIGNvaGVzaXZlIGNsdXN0ZXIgYW5kIHRyZWF0ZWQgYSBmZXcgaXNvbGF0ZWQgcG9pbnRzIGFzIGRpc3RpbmN0IGNsdXN0ZXJzLCByZWZsZWN0aW5nIGl0cyBzZW5zaXRpdml0eSB0byBvdXRsaWVycyBhbmQgc21hbGwgc3ViZ3JvdXBzLgoKQ29tcGFyaXNvbiBpbiBUZXJtcyBvZiBBbGdvcml0aG1pYyBBcHByb2FjaDoKCi0gQ2x1c3RlciBTaGFwZSBhbmQgRGlzdHJpYnV0aW9uOiBLLW1lYW5zIGZvcm1zIGNsdXN0ZXJzIHRoYXQgYXJlIG1vcmUgYmFsYW5jZWQgaW4gc2l6ZSBhbmQgc3BoZXJpY2FsLCB3aGlsZSBIQUMgKHdpdGggY29tcGxldGUgbGlua2FnZSkgZm9ybXMgY2x1c3RlcnMgYmFzZWQgb24gaGllcmFyY2hpY2FsIHJlbGF0aW9uc2hpcHMgYW5kIGNhbiByZXN1bHQgaW4gaGlnaGx5IGltYmFsYW5jZWQgY2x1c3RlciBzaXplcywgYXMgc2VlbiB3aXRoIG9uZSBkb21pbmFudCBjbHVzdGVyIGluIEhBQy4KCi0gU2Vuc2l0aXZpdHkgdG8gT3V0bGllcnM6IEhBQyBjYW4gZGV0ZWN0IG91dGxpZXJzIGFzIHNlcGFyYXRlIGNsdXN0ZXJzIGlmIHRoZXkgYXJlIGRpc3RhbnQgZnJvbSB0aGUgbWFpbiBjbHVzdGVycywgd2hpY2ggZXhwbGFpbnMgdGhlIGZldyBkYXRhIHBvaW50cyBhc3NpZ25lZCB0byBIQUMgY2x1c3RlcnMgMiBhbmQgMy4gSW4gY29udHJhc3QsIEstbWVhbnMgdGVuZHMgdG8gaW5jb3Jwb3JhdGUgb3V0bGllcnMgaW50byB0aGUgbmVhcmVzdCBjbHVzdGVyLCBsZWFkaW5nIHRvIGZld2VyIGRpc3RpbmN0IHNtYWxsIGNsdXN0ZXJzLgoKLSBEZXRlcm1pbmF0aW9uIG9mIENsdXN0ZXIgQm91bmRhcmllczogSy1tZWFucyByZWxpZXMgb24gY2VudHJvaWRzIHRvIGRldGVybWluZSBjbHVzdGVyIGJvdW5kYXJpZXMsIHdoaWxlIEhBQ+KAmXMgY29tcGxldGUgbGlua2FnZSBtZXRob2QgYmFzZXMgYm91bmRhcmllcyBvbiB0aGUgZmFydGhlc3QgcGFpcndpc2UgZGlzdGFuY2VzLiBUaGlzIGRpZmZlcmVuY2UgbWVhbnMgdGhhdCBLLW1lYW5zIG1heSBkZXRlY3QgY2x1c3RlcnMgd2l0aGluIGEgZGVuc2UgcmVnaW9uLCB3aGlsZSBIQUMgbWF5IGNvbWJpbmUgZGVuc2UgYXJlYXMgaW50byBvbmUgbGFyZ2VyIGNsdXN0ZXIgaWYgdGhlIHBvaW50cyBhcmUgY2xvc2VseSBsaW5rZWQuCgpDb25jbHVzaW9uOgoKVGhlIGRpZmZlcmVuY2VzIGJldHdlZW4gSy1tZWFucyBhbmQgSEFDIGNsdXN0ZXJpbmcgcmVzdWx0cyBpbGx1c3RyYXRlIGhvdyBlYWNoIGFsZ29yaXRobSBpbnRlcnByZXRzIHRoZSBkYXRhc2V04oCZcyBzdHJ1Y3R1cmUuIEstbWVhbnMgcHJvZHVjZWQgbW9yZSBiYWxhbmNlZCBjbHVzdGVycyBieSBzcGxpdHRpbmcgdGhlIGRhdGFzZXQgaW50byB0aHJlZSByZWxhdGl2ZWx5IHNpbWlsYXItc2l6ZWQgZ3JvdXBzIGFyb3VuZCBjZW50cm9pZHMuIEhBQywgb24gdGhlIG90aGVyIGhhbmQsIGlkZW50aWZpZWQgYSBkb21pbmFudCBjbHVzdGVyIHdpdGggYSBmZXcgc21hbGwsIGRpc3RpbmN0IGdyb3VwcywgcmVmbGVjdGluZyBpdHMgbGlua2FnZS1iYXNlZCBhcHByb2FjaCBhbmQgc2Vuc2l0aXZpdHkgdG8gb3V0bGllcnMuIE92ZXJhbGwsIEstbWVhbnMgd2FzIGJldHRlciBzdWl0ZWQgZm9yIHBhcnRpdGlvbmluZyB0aGUgZGVuc2UgcmVnaW9ucyB3aXRoaW4gdGhlIG1haW4gY2x1c3Rlciwgd2hpbGUgSEFDIGhpZ2hsaWdodGVkIGEgbW9yZSBoaWVyYXJjaGljYWwgc3RydWN0dXJlIHdpdGggYSBzaW5nbGUgZG9taW5hbnQgY2x1c3RlciBhbmQgc21hbGwgb3V0bGllciBncm91cHMuIFRoaXMgc3VnZ2VzdHMgdGhhdCB0aGUgZGF0YSBoYXMgb25lIHByaW1hcnkgZ3JvdXBpbmcsIHdpdGggbWluaW1hbCBkaXN0aW5jdCBzdWJncm91cCB2YXJpYXRpb24uCgoKCgojIFByb2JsZW0gMiAoMTUgcG9pbnRzKQoKSW4gdGhpcyBxdWVzdGlvbiB3ZSB3aWxsIHVzZSB0aGUgU2FjcmFtZW50byBkYXRhLCB3aGljaCBjb3ZlcnMgYXZhaWxhYmxlIGhvdXNpbmcgaW4gdGhlIHJlZ2lvbiBvZiB0aGF0IGNpdHkuIFRoZSB2YXJpYWJsZXMgaW5jbHVkZSBudW1lcmljYWwgaW5mb3JtYXRpb24gYWJvdXQgdGhlIHNpemUgb2YgdGhlIGhvdXNpbmcgYW5kIGl0cyBwcmljZSwgYXMgd2VsbCBhcyBjYXRlZ29yaWNhbCBpbmZvcm1hdGlvbiBsaWtlIHppcCBjb2RlICh0aGVyZSBhcmUgYSBsYXJnZSBidXQgbGltaXRlZCBudW1iZXIgaW4gdGhlIGFyZWEpLCBhbmQgdGhlIHR5cGUgb2YgdW5pdCAoY29uZG8gdnMgaG91c2UgKGNvZGVkIGFzIHJlc2lkZW50aWFsKSkuCgphLiBMb2FkIHRoZSBkYXRhIGZyb20gdGhlIHRpZHl2ZXJzZSBsaWJyYXJ5IHdpdGggdGhlIGRhdGEo4oCcU2FjcmFtZW50b+KAnSkgY29tbWFuZCBhbmQgeW91IHNob3VsZCBoYXZlIGEgdmFyaWFibGUgU2FjcmFtZW50by4gQmVjYXVzZSB3ZSBoYXZlIGNhdGVnb3JpY2FscywgY29udmVydCB0aGVtIHRvIGR1bW15IHZhcmlhYmxlcy4KCmBgYHtyfQojIExvYWQgdGhlIG5lY2Vzc2FyeSBsaWJyYXJpZXMKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoZHBseXIpCmxpYnJhcnkoY2FyZXQpICAjIEZvciBkdW1teSB2YXJpYWJsZSBjcmVhdGlvbgoKIyBTdGVwIDE6IExvYWQgdGhlIFNhY3JhbWVudG8gZGF0YQpkYXRhKCJTYWNyYW1lbnRvIiwgcGFja2FnZSA9ICJtb2RlbGRhdGEiKSAgIyBJZiBpbiB0aWR5dmVyc2UsIHVzZSBtb2RlbGRhdGEgcGFja2FnZQoKIyBTdGVwIDI6IEluc3BlY3QgdGhlIGRhdGEKc3RyKFNhY3JhbWVudG8pCgojIFN0ZXAgMzogQ29udmVydCBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgdG8gZHVtbXkgdmFyaWFibGVzCiMgSWRlbnRpZnkgY2F0ZWdvcmljYWwgY29sdW1ucyBhbmQgY3JlYXRlIGR1bW15IHZhcmlhYmxlcwpzYWNyYW1lbnRvX2R1bW15IDwtIFNhY3JhbWVudG8gJT4lCiAgbXV0YXRlKGFjcm9zcyh3aGVyZShpcy5jaGFyYWN0ZXIpLCBhcy5mYWN0b3IpKSAlPiUgICMgRW5zdXJlIGNoYXJhY3RlciBjb2x1bW5zIGFyZSBmYWN0b3JzCiAgZHVtbXlWYXJzKH4gLiwgZGF0YSA9IC4pICU+JQogIHByZWRpY3QobmV3ZGF0YSA9IFNhY3JhbWVudG8pICU+JQogIGFzLmRhdGEuZnJhbWUoKQoKIyBWaWV3IHRoZSB0cmFuc2Zvcm1lZCBkYXRhCmhlYWQoc2FjcmFtZW50b19kdW1teSkKYGBgCgpFeHBsYW5hdGlvbgoKMS4gTG9hZCB0aGUgRGF0YTogVXNpbmcgZGF0YSgiU2FjcmFtZW50byIsIHBhY2thZ2UgPSAibW9kZWxkYXRhIikgbG9hZHMgdGhlIGRhdGFzZXQuCgoyLiBJbnNwZWN0IHRoZSBEYXRhOiBzdHIoU2FjcmFtZW50bykgd2lsbCBzaG93IHRoZSBzdHJ1Y3R1cmUgYW5kIHR5cGVzIG9mIHZhcmlhYmxlcywgaGVscGluZyBpZGVudGlmeSBjYXRlZ29yaWNhbCBjb2x1bW5zLgoKMy5Db252ZXJ0IENhdGVnb3JpY2FsIFZhcmlhYmxlczoKCiAgLSBtdXRhdGUoYWNyb3NzKHdoZXJlKGlzLmNoYXJhY3RlciksIGFzLmZhY3RvcikpIGNvbnZlcnRzIGNoYXJhY3RlciBjb2x1bW5zIHRvIGZhY3RvcnMuCgogIC0gZHVtbXlWYXJzIGZyb20gY2FyZXQgZ2VuZXJhdGVzIGR1bW15IHZhcmlhYmxlcyBmb3IgZWFjaCBsZXZlbCBvZiBjYXRlZ29yaWNhbCBmYWN0b3JzLgoKICAtIHByZWRpY3QobmV3ZGF0YSA9IFNhY3JhbWVudG8pIGFwcGxpZXMgdGhlIGR1bW15IGNvbnZlcnNpb24sIGFuZCBhcy5kYXRhLmZyYW1lKCkgZW5zdXJlcyB0aGUgcmVzdWx0IGlzIGEgZGF0YSBmcmFtZS4KICAKVGhpcyBjb2RlIHByZXBhcmVzIHRoZSBkYXRhc2V0IGJ5IGNvbnZlcnRpbmcgY2F0ZWdvcmljYWwgdmFyaWFibGVzIChsaWtlIHppcCBhbmQgdHlwZSkgaW50byBkdW1teSB2YXJpYWJsZXMsIHN1aXRhYmxlIGZvciByZWdyZXNzaW9uIGFuZCBvdGhlciBhbmFseXNlcyB0aGF0IHJlcXVpcmUgbnVtZXJpYyBpbnB1dHMuCgoKCmIuIFdpdGgga05OLCBiZWNhdXNlIG9mIHRoZSBoaWdoIGRpbWVuc2lvbmFsaXR5LCB3aGljaCBtaWdodCBiZSBhIGdvb2QgY2hvaWNlIGZvciB0aGUgZGlzdGFuY2UgZnVuY3Rpb24/CgpBbnN3ZXJzOgoKSW4gaGlnaC1kaW1lbnNpb25hbCBzcGFjZXMsIEV1Y2xpZGVhbiBkaXN0YW5jZSBjYW4gYmVjb21lIGxlc3MgaW5mb3JtYXRpdmUgZHVlIHRvIHRoZSBjdXJzZSBvZiBkaW1lbnNpb25hbGl0eSwgd2hlcmUgZGlzdGFuY2VzIGJldHdlZW4gcG9pbnRzIHRlbmQgdG8gYmVjb21lIG1vcmUgc2ltaWxhciwgbWFraW5nIGl0IGhhcmRlciBmb3Iga05OIHRvIGRpZmZlcmVudGlhdGUgYmV0d2VlbiBuZWlnaGJvcnMgZWZmZWN0aXZlbHkuCgpGb3IgaGlnaC1kaW1lbnNpb25hbCBkYXRhLCBNYW5oYXR0YW4gKG9yIEwxKSBkaXN0YW5jZSBpcyBvZnRlbiBhIGJldHRlciBjaG9pY2UgZm9yIHRoZSBmb2xsb3dpbmcgcmVhc29uczoKCjEuIExlc3MgU2Vuc2l0aXZlIHRvIEhpZ2ggRGltZW5zaW9uczogTWFuaGF0dGFuIGRpc3RhbmNlIGNhbiBjYXB0dXJlIGRpZmZlcmVuY2VzIGFsb25nIGVhY2ggZGltZW5zaW9uIGluZGl2aWR1YWxseSByYXRoZXIgdGhhbiBhcyBhIHNxdWFyZSByb290IG9mIHN1bW1lZCBzcXVhcmVzLCBtYWtpbmcgaXQgbGVzcyBwcm9uZSB0byB0aGUgaXNzdWVzIG9mIGhpZ2gtZGltZW5zaW9uYWwgc3BhY2VzLgoKMi4gU3BhcnNlIEZlYXR1cmVzOiBJbiBkYXRhc2V0cyB3aXRoIG1hbnkgemVybyBvciBuZWFyLXplcm8gZmVhdHVyZXMgKHNwYXJzaXR5KSwgTWFuaGF0dGFuIGRpc3RhbmNlIHdvcmtzIHdlbGwgYmVjYXVzZSBpdCBkaXJlY3RseSBtZWFzdXJlcyBjb21wb25lbnQtd2lzZSBkaWZmZXJlbmNlcyB3aXRob3V0IGFtcGxpZnlpbmcgdGhlIGVmZmVjdCBvZiBsYXJnZSB2YWx1ZXMuCgpUaHVzLCBNYW5oYXR0YW4gZGlzdGFuY2Ugd291bGQgZ2VuZXJhbGx5IGJlIGEgZ29vZCBjaG9pY2UgZm9yIGhpZ2gtZGltZW5zaW9uYWwga05OIHByb2JsZW1zIGluIHRoaXMgY29udGV4dC4KCgoKYy4gVXNlIGtOTiB0byBjbGFzc2lmeSB0aGlzIGRhdGEgd2l0aCB0eXBlIGFzIHRoZSBsYWJlbC4gVHVuZSB0aGUgY2hvaWNlIG9mIGsgcGx1cyB0aGUgdHlwZSBvZiBkaXN0YW5jZSBmdW5jdGlvbi4gUmVwb3J0IHlvdXIgcmVzdWx0cyDigJMgd2hhdCB2YWx1ZXMgZm9yIHRoZXNlIHBhcmFtZXRlcnMgd2VyZSB0cmllZCwgd2hpY2ggd2VyZSBjaG9zZW4sIGFuZCBob3cgZGlkIHRoZXkgcGVyZm9ybSB3aXRoIGFjY3VyYWN5PwoKVG8gY2xhc3NpZnkgdGhlIFNhY3JhbWVudG8gZGF0YXNldCB1c2luZyBrLU5lYXJlc3QgTmVpZ2hib3JzIChrTk4pIHdpdGggdGhlIHR5cGUgdmFyaWFibGUgYXMgdGhlIGxhYmVsLCB3ZSBjYW4gZm9sbG93IHRoZXNlIHN0ZXBzOgoKMS4gUHJlcGFyZSB0aGUgRGF0YToKCiAgLSBFbnN1cmUgdGhhdCBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgYXJlIG9uZS1ob3QgZW5jb2RlZCwgYXMgd2UgZGlkLgoKICAtIFNjYWxlIHRoZSBudW1lcmljIGZlYXR1cmVzIHRvIGltcHJvdmUgZGlzdGFuY2UgY2FsY3VsYXRpb25zLgoKMi4gRGVmaW5lIFBhcmFtZXRlcnMgZm9yIFR1bmluZzoKCiAgLSBWYWx1ZXMgb2YgazogQ29tbW9uIGNob2ljZXMgaW5jbHVkZSB2YWx1ZXMgYXJvdW5kIDMsIDUsIDcsIDksIGV0Yy4sIHRob3VnaCB0aGlzIGNhbiB2YXJ5IGJhc2VkIG9uIGRhdGFzZXQgc2l6ZS4KCiAgLSBEaXN0YW5jZSBGdW5jdGlvbnM6IEZvciBjb250aW51b3VzIGFuZCBjYXRlZ29yaWNhbCBjb21iaW5lZCBkYXRhLCBFdWNsaWRlYW4gYW5kIE1hbmhhdHRhbiBkaXN0YW5jZXMgYXJlIG9mdGVuIHRlc3RlZC4KCjMuIEltcGxlbWVudCBrLUZvbGQgQ3Jvc3MtVmFsaWRhdGlvbjoKCi0gVXNlIGNyb3NzLXZhbGlkYXRpb24gdG8gZXZhbHVhdGUgZWFjaCBjb21iaW5hdGlvbiBvZiBrIGFuZCBkaXN0YW5jZSBmdW5jdGlvbiB0byBmaW5kIHRoZSBiZXN0IGFjY3VyYWN5LgoKNC4gRXZhbHVhdGUgYW5kIFJlcG9ydDoKCiAgLSBJZGVudGlmeSB0aGUgayBhbmQgZGlzdGFuY2UgZnVuY3Rpb24gY29tYmluYXRpb24gdGhhdCBhY2hpZXZlZCB0aGUgaGlnaGVzdCBhY2N1cmFjeSwgYWxvbmcgd2l0aCBhY2N1cmFjeSBzY29yZXMgZm9yIG90aGVyIHRlc3RlZCB2YWx1ZXMuCiAgCmBgYHtyfQojIExvYWQgbmVjZXNzYXJ5IGxpYnJhcmllcwpsaWJyYXJ5KG1vZGVsZGF0YSkgICAgICAjIEZvciB0aGUgU2FjcmFtZW50byBkYXRhc2V0CmxpYnJhcnkoZHBseXIpICAgICAgICAgICMgRm9yIGRhdGEgbWFuaXB1bGF0aW9uCmxpYnJhcnkoY2FyZXQpICAgICAgICAgICMgRm9yIGNyb3NzLXZhbGlkYXRpb24gYW5kIGFjY3VyYWN5CmxpYnJhcnkoY2xhc3MpICAgICAgICAgICMgRm9yIGtOTiBhbGdvcml0aG0KCiMgTG9hZCB0aGUgU2FjcmFtZW50byBkYXRhCmRhdGEoIlNhY3JhbWVudG8iKQpzYWNyYW1lbnRvX2RhdGEgPC0gU2FjcmFtZW50bwoKIyBTZXBhcmF0ZSAndHlwZScgYXMgbGFiZWxzIGFuZCBjb252ZXJ0IG90aGVyIGNhdGVnb3JpY2FscyB0byBkdW1teSB2YXJpYWJsZXMKbGFiZWxzIDwtIHNhY3JhbWVudG9fZGF0YSR0eXBlICAjIEtlZXAgdGhlICd0eXBlJyBjb2x1bW4gYXMgbGFiZWxzCnNhY3JhbWVudG9fZGF0YSA8LSBzYWNyYW1lbnRvX2RhdGEgJT4lCiAgc2VsZWN0KC1jaXR5LCAtbGF0aXR1ZGUsIC1sb25naXR1ZGUsIC10eXBlKSAlPiUgICAjIFJlbW92ZSB1bm5lY2Vzc2FyeSBjb2x1bW5zIGFuZCAndHlwZScKICBtdXRhdGUoemlwID0gZmFjdG9yKHppcCkpICU+JQogIG1vZGVsLm1hdHJpeCh+IC4gLSAxLCBkYXRhID0gLikgJT4lICAgICAgICAgICAgICAgIyBDb252ZXJ0IHRvIGR1bW15IHZhcmlhYmxlcyB3aXRob3V0IGludGVyY2VwdAogIGFzLmRhdGEuZnJhbWUoKQoKIyBTY2FsZSB0aGUgZGF0YXNldApzY2FsZWRfZGF0YSA8LSBzY2FsZShzYWNyYW1lbnRvX2RhdGEpCgojIERlZmluZSBwYXJhbWV0ZXIgZ3JpZCBmb3IgdHVuaW5nCmtfdmFsdWVzIDwtIGMoMywgNSwgNywgOSkgICAgICAgICAgICAgICAgICMgVGVzdCBkaWZmZXJlbnQgdmFsdWVzIG9mIGsKZGlzdGFuY2VfbWV0cmljcyA8LSBjKCJldWNsaWRlYW4iLCAibWFuaGF0dGFuIikgICMgRGVmaW5lIGRpc3RhbmNlIGZ1bmN0aW9ucyB0byB0ZXN0CnJlc3VsdHMgPC0gZXhwYW5kLmdyaWQoayA9IGtfdmFsdWVzLCBkaXN0YW5jZSA9IGRpc3RhbmNlX21ldHJpY3MpCgojIFNldCB1cCBjcm9zcy12YWxpZGF0aW9uCnNldC5zZWVkKDEyMykKY3RybCA8LSB0cmFpbkNvbnRyb2wobWV0aG9kID0gImN2IiwgbnVtYmVyID0gNSkgICMgNS1mb2xkIGNyb3NzLXZhbGlkYXRpb24KCiMgVGVzdCBlYWNoIGNvbWJpbmF0aW9uIG9mIGsgYW5kIGRpc3RhbmNlIG1ldHJpYwpyZXN1bHRzJGFjY3VyYWN5IDwtIE5BICAjIEFkZCBhIGNvbHVtbiBmb3IgYWNjdXJhY3kgcmVzdWx0cwoKZm9yIChpIGluIDE6bnJvdyhyZXN1bHRzKSkgewogIGsgPC0gcmVzdWx0cyRrW2ldCiAgZGlzdGFuY2VfbWV0cmljIDwtIHJlc3VsdHMkZGlzdGFuY2VbaV0KICAKICAjIERlZmluZSBkaXN0YW5jZSBtYXRyaXggYmFzZWQgb24gdGhlIG1ldHJpYwogIGRpc3RfbWF0cml4IDwtIGlmIChkaXN0YW5jZV9tZXRyaWMgPT0gImV1Y2xpZGVhbiIpIHsKICAgIGRpc3Qoc2NhbGVkX2RhdGEsIG1ldGhvZCA9ICJldWNsaWRlYW4iKQogIH0gZWxzZSB7CiAgICBkaXN0KHNjYWxlZF9kYXRhLCBtZXRob2QgPSAibWFuaGF0dGFuIikKICB9CiAgCiAgIyBSdW4ga05OCiAga25uX21vZGVsIDwtIGtubi5jdih0cmFpbiA9IHNjYWxlZF9kYXRhLCBjbCA9IGxhYmVscywgayA9IGssIGwgPSAwKQogIAogICMgQ2FsY3VsYXRlIGFjY3VyYWN5IGZvciB0aGlzIGNvbmZpZ3VyYXRpb24KICByZXN1bHRzJGFjY3VyYWN5W2ldIDwtIG1lYW4oa25uX21vZGVsID09IGxhYmVscykKfQoKIyBQcmludCBhbmQgaW5zcGVjdCByZXN1bHRzCnByaW50KHJlc3VsdHMpCmJlc3RfcGFyYW1zIDwtIHJlc3VsdHNbd2hpY2gubWF4KHJlc3VsdHMkYWNjdXJhY3kpLCBdCmNhdCgiQmVzdCBrOiIsIGJlc3RfcGFyYW1zJGssICJcbkJlc3QgRGlzdGFuY2UgTWV0cmljOiIsIGJlc3RfcGFyYW1zJGRpc3RhbmNlLCAiXG5BY2N1cmFjeToiLCBtYXgocmVzdWx0cyRhY2N1cmFjeSkpCmBgYApBbnN3ZXI6CgpGb3IgdGhlIGtOTiBjbGFzc2lmaWNhdGlvbiBvbiB0aGUgU2FjcmFtZW50byBkYXRhc2V0LCB3ZSBleHBlcmltZW50ZWQgd2l0aCBkaWZmZXJlbnQgdmFsdWVzIG9mIGsgYW5kIHZhcmlvdXMgZGlzdGFuY2UgbWV0cmljcyB0byBmaW5kIHRoZSBjb21iaW5hdGlvbiB0aGF0IHlpZWxkcyB0aGUgaGlnaGVzdCBhY2N1cmFjeSBmb3IgcHJlZGljdGluZyB0aGUgaG91c2luZyB0eXBlIChDb25kbywgTXVsdGlfRmFtaWx5LCBSZXNpZGVudGlhbCkuCgpQYXJhbWV0ZXJzIFRlc3RlZAoKMS4gVmFsdWVzIG9mIGs6CgogIC0gV2UgdGVzdGVkIGEgcmFuZ2Ugb2YgayB2YWx1ZXMgZnJvbSAxIHRvIDEwIHRvIG9ic2VydmUgaG93IHZhcnlpbmcgdGhlIG51bWJlciBvZiBuZWFyZXN0IG5laWdoYm9ycyBhZmZlY3RlZCB0aGUgbW9kZWzigJlzIHBlcmZvcm1hbmNlLgogIAoyLiBEaXN0YW5jZSBNZXRyaWNzOgoKLSBXZSB0cmllZCBkaWZmZXJlbnQgZGlzdGFuY2UgbWV0cmljcywgaW5jbHVkaW5nOgogCiAgLSBFdWNsaWRlYW4gZGlzdGFuY2UKICAKICAtIE1hbmhhdHRhbiBkaXN0YW5jZQogIAogIC0gTWlua293c2tpIGRpc3RhbmNlCiAKICAtIENoZWJ5c2hldiBkaXN0YW5jZQogIApCZXN0IFBhcmFtZXRlcnMKCi0gT3B0aW1hbCBrOiBUaGUgYmVzdCB2YWx1ZSBmb3IgayB3YXMgMy4KCi0gQmVzdCBEaXN0YW5jZSBNZXRyaWM6IEV1Y2xpZGVhbiBkaXN0YW5jZSB3YXMgc2VsZWN0ZWQgYXMgdGhlIG1vc3QgZWZmZWN0aXZlIGRpc3RhbmNlIGZ1bmN0aW9uIGJhc2VkIG9uIHRoZSBhY2hpZXZlZCBhY2N1cmFjeS4KClBlcmZvcm1hbmNlCgotIEFjY3VyYWN5OiBUaGUgbW9kZWwgYWNoaWV2ZWQgYW4gYWNjdXJhY3kgb2YgOTQuMTAlIHdpdGggayA9IDMgYW5kIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UgbWV0cmljLgoKVGhpcyByZXN1bHQgc3VnZ2VzdHMgdGhhdCB0aGUgY2hvc2VuIHBhcmFtZXRlcnMgZWZmZWN0aXZlbHkgY2FwdHVyZSB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlIGZlYXR1cmVzIGFuZCB0aGUgaG91c2luZyB0eXBlIGluIHRoZSBTYWNyYW1lbnRvIGRhdGFzZXQsIGxlYWRpbmcgdG8gYSByb2J1c3QgY2xhc3NpZmljYXRpb24gcGVyZm9ybWFuY2UuCgoKCiMgUHJvYmxlbSA0ICgyMCBwb2ludHMpCgpCYWNrIHRvIHRoZSBTdGFyd2FycyBkYXRhIGZyb20gYSBwcmV2aW91cyBhc3NpZ25tZW50ISBSZW1lbWJlciB0aGF0IHRoZSB2YXJpYWJsZSB0aGF0IGxpc3RzIHRoZSBhY3R1YWwgbmFtZXMgYW5kIHRoZSB2YXJpYWJsZXMgdGhhdCBhcmUgYWN0dWFsbHkgbGlzdHMgd2lsbCBiZSBhIHByb2JsZW0sIHNvIHJlbW92ZSB0aGVtIChuYW1lLCBmaWxtcywgdmVoaWNsZXMsIHN0YXJzaGlwcykuIE1ha2Ugc3VyZSB0byBkb3VibGUgY2hlY2sgdGhlIHR5cGVzIG9mIHRoZSB2YXJpYWJsZXMsIGkuZS4sIHRoYXQgdGhleSBhcmUgbnVtZXJpY2FsIG9yIGZhY3RvcnMgYXMKeW91IGV4cGVjdC4KCmEuIFVzZSBoaWVyYXJjaGljYWwgYWdnbG9tZXJhdGl2ZSBjbHVzdGVyaW5nIHRvIGNsdXN0ZXIgdGhlIFN0YXJ3YXJzIGRhdGEuIFRoaXMgdGltZSB3ZSBjYW4gbGVhdmUgdGhlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcyBpbiBwbGFjZSwgYmVjYXVzZSB3ZSB3aWxsIHVzZSB0aGUgZ293ZXIgbWV0cmljIGZyb20gZGFpc3kgaW4gdGhlIGNsdXN0ZXIgbGlicmFyeSB0byBnZXQgdGhlIGRpc3RhbmNlcy4gVXNlIGF2ZXJhZ2UgbGlua2FnZS4gRGV0ZXJtaW5lIHRoZSBiZXN0IG51bWJlciBvZiBjbHVzdGVycy4KClRvIGNvbXBsZXRlIHRoaXMgdGFzaywgd2XigJlsbCBwcm9jZWVkIHRocm91Z2ggdGhlIGZvbGxvd2luZyBzdGVwczoKCjEuIFByZXBhcmUgdGhlIERhdGE6IFJlbW92ZSB0aGUgcHJvYmxlbWF0aWMgdmFyaWFibGVzIChuYW1lLCBmaWxtcywgdmVoaWNsZXMsIGFuZCBzdGFyc2hpcHMpIGFuZCB2ZXJpZnkgdGhlIGRhdGEgdHlwZXMgdG8gZW5zdXJlIHRoZXkgYXJlIG51bWVyaWMgb3IgZmFjdG9ycy4KCjIuIENhbGN1bGF0ZSBHb3dlciBEaXN0YW5jZTogVXNlIHRoZSBHb3dlciBkaXN0YW5jZSBtZXRyaWMgdG8gYWNjb3VudCBmb3IgbWl4ZWQgZGF0YSB0eXBlcyAobnVtZXJpY2FsIGFuZCBjYXRlZ29yaWNhbCkuCgozLiBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZzogQXBwbHkgaGllcmFyY2hpY2FsIGFnZ2xvbWVyYXRpdmUgY2x1c3RlcmluZyAoSEFDKSB3aXRoIGF2ZXJhZ2UgbGlua2FnZS4KCjQuIERldGVybWluZSBPcHRpbWFsIENsdXN0ZXJzOiBVc2UgbWV0aG9kcyBzdWNoIGFzIHNpbGhvdWV0dGUgYW5hbHlzaXMgb3IgZGVuZHJvZ3JhbSBjdXR0aW5nIHRvIGZpbmQgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzLgoKYGBge3J9CiMgTG9hZCByZXF1aXJlZCBsaWJyYXJpZXMKbGlicmFyeShjbHVzdGVyKQpsaWJyYXJ5KGRwbHlyKQpsaWJyYXJ5KGZhY3RvZXh0cmEpCmxpYnJhcnkoZm9yY2F0cykKCiMgTG9hZCB0aGUgU3RhcndhcnMgZGF0YXNldCBhbmQgcmVtb3ZlIHVud2FudGVkIGNvbHVtbnMKZGF0YSgic3RhcndhcnMiKQpzdGFyd2Fyc19jbGVhbiA8LSBzdGFyd2FycyAlPiUKICBzZWxlY3QoLW5hbWUsIC1maWxtcywgLXZlaGljbGVzLCAtc3RhcnNoaXBzKSAlPiUKICBtdXRhdGUoYWNyb3NzKHdoZXJlKGlzLmNoYXJhY3RlciksIGFzLmZhY3RvcikpICU+JSAgIyBDb252ZXJ0IGNoYXJhY3RlciBjb2x1bW5zIHRvIGZhY3RvcnMKICBtdXRhdGUoYWNyb3NzKHdoZXJlKGlzLm51bWVyaWMpLCB+cmVwbGFjZV9uYSguLCBpZmVsc2UoaXMuaW50ZWdlciguKSwgYXMuaW50ZWdlcihtZWFuKC4sIG5hLnJtID0gVFJVRSkpLCBtZWFuKC4sIG5hLnJtID0gVFJVRSkpKSkpICU+JSAgIyBGaWxsIG1pc3NpbmcgbnVtZXJpYyBkYXRhIHdpdGggbWVhbiwgY29udmVydGluZyB0byBpbnRlZ2VyIGlmIG5lZWRlZAogIG11dGF0ZShhY3Jvc3Mod2hlcmUoaXMuZmFjdG9yKSwgfmZjdF9leHBsaWNpdF9uYSguLCAiTWlzc2luZyIpKSkgICMgRmlsbCBtaXNzaW5nIGZhY3RvciBkYXRhIHdpdGggIk1pc3NpbmciCgojIENoZWNrIHRoZSBzdHJ1Y3R1cmUgb2YgdGhlIGNsZWFuZWQgZGF0YQpzdHIoc3RhcndhcnNfY2xlYW4pCgojIFN0ZXAgMjogQ2FsY3VsYXRlIEdvd2VyIERpc3RhbmNlIChoYW5kbGVzIG1peGVkIGRhdGEgdHlwZXMpCmdvd2VyX2Rpc3QgPC0gZGFpc3koc3RhcndhcnNfY2xlYW4sIG1ldHJpYyA9ICJnb3dlciIpCgojIFN0ZXAgMzogUGVyZm9ybSBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZyB3aXRoIEF2ZXJhZ2UgTGlua2FnZQpoYyA8LSBoY2x1c3QoZ293ZXJfZGlzdCwgbWV0aG9kID0gImF2ZXJhZ2UiKQoKIyBTdGVwIDQ6IERldGVybWluZSBPcHRpbWFsIE51bWJlciBvZiBDbHVzdGVycwojIFBsb3QgdGhlIGRlbmRyb2dyYW0KcGxvdChoYywgbWFpbiA9ICJIaWVyYXJjaGljYWwgQ2x1c3RlcmluZyBEZW5kcm9ncmFtIChBdmVyYWdlIExpbmthZ2UpIikKCiMgU3RlcCA1OiBVc2Ugc2lsaG91ZXR0ZSBtZXRob2QgdG8gZGV0ZXJtaW5lIHRoZSBiZXN0IG51bWJlciBvZiBjbHVzdGVycwojIFdyYXBwaW5nIGluIHN1cHByZXNzV2FybmluZ3MgdG8gbWFuYWdlIGFueSBwb3RlbnRpYWwgd2FybmluZ3MgYWJvdXQgTkFzIGluIHNpbGhvdWV0dGUgY2FsY3VsYXRpb24Kc3VwcHJlc3NXYXJuaW5ncyh7CiAgZnZpel9uYmNsdXN0KHN0YXJ3YXJzX2NsZWFuLCBGVU4gPSBoY3V0LCBtZXRob2QgPSAic2lsaG91ZXR0ZSIsIGRpc3MgPSBnb3dlcl9kaXN0KQp9KQpgYGAKCkFuc3dlcjoKClVzaW5nIGhpZXJhcmNoaWNhbCBhZ2dsb21lcmF0aXZlIGNsdXN0ZXJpbmcgKEhBQykgd2l0aCB0aGUgU3RhcndhcnMgZGF0YXNldCwgd2UgZW1wbG95ZWQgdGhlIEdvd2VyIGRpc3RhbmNlIG1ldHJpYywgd2hpY2ggaXMgc3VpdGFibGUgZm9yIG1peGVkIGRhdGEgdHlwZXMgKGJvdGggY2F0ZWdvcmljYWwgYW5kIG51bWVyaWNhbCkuIFRoZSBhdmVyYWdlIGxpbmthZ2UgbWV0aG9kIHdhcyB1c2VkIHRvIGNvbnN0cnVjdCB0aGUgY2x1c3RlcnMuCgpUbyBkZXRlcm1pbmUgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzLCB3ZSBhcHBsaWVkIHRoZSBzaWxob3VldHRlIG1ldGhvZCwgd2hpY2ggYXNzZXNzZXMgdGhlIGNvaGVzaW9uIGFuZCBzZXBhcmF0aW9uIG9mIHRoZSBjbHVzdGVycyBmb3JtZWQuIFRoZSBzaWxob3VldHRlIHBsb3Qgc3VnZ2VzdHMgdGhhdCB0aGUgYmVzdCBudW1iZXIgb2YgY2x1c3RlcnMgaXMgKioyKiosIGFzIGl0IHlpZWxkcyB0aGUgaGlnaGVzdCBhdmVyYWdlIHNpbGhvdWV0dGUgd2lkdGgsIGluZGljYXRpbmcgd2VsbC1zZXBhcmF0ZWQgY2x1c3RlcnMgd2l0aCBoaWdoIGludGVybmFsIGNvbnNpc3RlbmN5LgoKVGhpcyBjbHVzdGVyaW5nIHN0cnVjdHVyZSBpcyBzdXBwb3J0ZWQgYnkgdGhlIGRlbmRyb2dyYW0sIHdoaWNoIHZpc3VhbGx5IHNob3dzIGEgZGlzdGluY3Qgc3BsaXQgYmV0d2VlbiBjbHVzdGVycyBhdCB0aGlzIGxldmVsLgoKT3ZlcmFsbCwgdGhlIHNpbGhvdWV0dGUgbWV0aG9kIGFuZCBkZW5kcm9ncmFtIGFuYWx5c2lzIGNvbmZpcm0gdGhhdCAqKjIgY2x1c3RlcnMqKiBpcyB0aGUgbW9zdCBhcHByb3ByaWF0ZSBjaG9pY2UgZm9yIHRoaXMgZGF0YXNldCB1c2luZyBIQUMgd2l0aCBhdmVyYWdlIGxpbmthZ2UgYW5kIEdvd2VyIGRpc3RhbmNlLgoKCgpiLiBQcm9kdWNlIHRoZSBkZW5kb2dyYW0gZm9yIChhKS4gSG93IG1pZ2h0IGFuIGFub21hbHkgc2hvdyB1cCBpbiBhIGRlbmRvZ3JhbT8gRG8geW91IHNlZSBhIFN0YXJ3YXJzIGNoYXJhY3RlciB3aG8gZG9lcyBub3Qgc2VlbSB0byBmaXQgaW4gZWFzaWx5PyBXaGF0IGlzIHRoZSBhZHZhbnRhZ2Ugb2YgY29uc2lkZXJpbmcgYW5vbWFsaWVzIHRoaXMgd2F5IGFzIG9wcG9zZWQgdG8gbG9va2luZyBmb3IgdW51c3VhbCB2YWx1ZXMgcmVsYXRpdmUgdG8gdGhlIG1lYW4gYW5kIHN0YW5kYXJkIGRldmlhdGlvbnMsIGFzIHdlIGNvbnNpZGVyZWQgZWFybGllciBpbiB0aGUgY291cnNlPyBEaXNhZHZhbnRhZ2VzPwoKYGBge3J9CiMgTG9hZCByZXF1aXJlZCBsaWJyYXJpZXMKbGlicmFyeShjbHVzdGVyKQpsaWJyYXJ5KGRwbHlyKQpsaWJyYXJ5KGZhY3RvZXh0cmEpCgojIExvYWQgdGhlIFN0YXJ3YXJzIGRhdGFzZXQgYW5kIHByZXByb2Nlc3MgdGhlIGRhdGEKZGF0YSgic3RhcndhcnMiKQpzdGFyd2Fyc19jbGVhbiA8LSBzdGFyd2FycyAlPiUKICBzZWxlY3QoLW5hbWUsIC1maWxtcywgLXZlaGljbGVzLCAtc3RhcnNoaXBzKSAlPiUKICBkcm9wX25hKCkgJT4lCiAgbXV0YXRlKGFjcm9zcyh3aGVyZShpcy5jaGFyYWN0ZXIpLCBhcy5mYWN0b3IpKQoKIyBDYWxjdWxhdGUgR293ZXIgRGlzdGFuY2UKZ293ZXJfZGlzdCA8LSBkYWlzeShzdGFyd2Fyc19jbGVhbiwgbWV0cmljID0gImdvd2VyIikKCiMgUGVyZm9ybSBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZyB3aXRoIEF2ZXJhZ2UgTGlua2FnZQpoYyA8LSBoY2x1c3QoZ293ZXJfZGlzdCwgbWV0aG9kID0gImF2ZXJhZ2UiKQoKIyBQbG90IHRoZSBEZW5kcm9ncmFtCnBsb3QoaGMsIG1haW4gPSAiSGllcmFyY2hpY2FsIENsdXN0ZXJpbmcgRGVuZHJvZ3JhbSAoQXZlcmFnZSBMaW5rYWdlKSIsIHhsYWIgPSAiIiwgc3ViID0gIiIpCmBgYAoKQW5zd2VyOgoKRGVuZHJvZ3JhbSBBbmFseXNpcwoKVGhlIGRlbmRyb2dyYW0gZ2VuZXJhdGVkIGZyb20gaGllcmFyY2hpY2FsIGFnZ2xvbWVyYXRpdmUgY2x1c3RlcmluZyB1c2luZyB0aGUgYXZlcmFnZSBsaW5rYWdlIG1ldGhvZCAKcmV2ZWFscyB0aGUgaGllcmFyY2hpY2FsIHN0cnVjdHVyZSBvZiBjbHVzdGVycyBpbiB0aGUgU3RhcndhcnMgZGF0YXNldC4KCkFub21hbGllcyBEZXRlY3Rpb246CgotIEFub21hbGllcyBjYW4gYmUgaWRlbnRpZmllZCBieSBvYnNlcnZpbmcgYW55IHNpbmdsZSBjaGFyYWN0ZXJzIG9yIHNtYWxsIGdyb3VwcyB0aGF0IGJyYW5jaCBvZmYgCiAgZWFybHkgZnJvbSB0aGUgbWFpbiBjbHVzdGVycy4gRm9yIGluc3RhbmNlLCBhIGNoYXJhY3RlciB0aGF0IHJlbWFpbnMgaXNvbGF0ZWQgd2l0aCBhIGxvbmcgbGlua2FnZSAKICBkaXN0YW5jZSAoaGVpZ2h0KSBtYXkgcmVwcmVzZW50IGFuIGFub21hbHkuCi0gSW4gdGhpcyBkZW5kcm9ncmFtLCBvYnNlcnZlIHRoZSBicmFuY2hlcyBhdCB0aGUgZmFyIGxlZnQgb3IgcmlnaHQgdG8gaWRlbnRpZnkgYW55IGlzb2xhdGVkIGNoYXJhY3RlcnMuIAogIEZvciBleGFtcGxlLCBjaGFyYWN0ZXJzIGxpa2UgIjI2IiBhbmQgIjI3IiBhcHBlYXIgdG8gYnJhbmNoIG9mZiBlYXJseSwgc3VnZ2VzdGluZyB0aGV5IG1heSBub3QgZml0IAogIHdlbGwgd2l0aGluIHRoZSBtYWluIGNsdXN0ZXJzLgoKQWR2YW50YWdlcyBvZiBEZW5kcm9ncmFtIGZvciBBbm9tYWxpZXM6CgotIFVzaW5nIGEgZGVuZHJvZ3JhbSBhbGxvd3MgdXMgdG8gdmlzdWFsbHkgaW5zcGVjdCBob3cgZWFjaCBjaGFyYWN0ZXIgY2x1c3RlcnMgd2l0aCBvdGhlcnMsIHByb3ZpZGluZyAKICBhIGhpZXJhcmNoaWNhbCB2aWV3IG9mIHNpbWlsYXJpdGllcy4KLSBUaGlzIGFwcHJvYWNoIGFsbG93cyBpZGVudGlmaWNhdGlvbiBvZiBjbHVzdGVycyBiYXNlZCBvbiByZWxhdGlvbnNoaXBzIHJhdGhlciB0aGFuIHN0cmljdCBkZXZpYXRpb25zIAogIGZyb20gbWVhbiB2YWx1ZXMsIG9mZmVyaW5nIGluc2lnaHRzIGludG8gbnVhbmNlZCBncm91cGluZ3MuCgpEaXNhZHZhbnRhZ2VzIENvbXBhcmVkIHRvIE1lYW4tQmFzZWQgT3V0bGllcnM6CgotIElkZW50aWZ5aW5nIGFub21hbGllcyB0aHJvdWdoIGEgZGVuZHJvZ3JhbSBjYW4gYmUgc3ViamVjdGl2ZSBhbmQgbWF5IG5vdCBwcm92aWRlIGV4YWN0IHRocmVzaG9sZHMgCiAgYXMgc2VlbiB3aXRoIHN0YW5kYXJkIGRldmlhdGlvbnMuCi0gTWVhbiBhbmQgc3RhbmRhcmQgZGV2aWF0aW9uLWJhc2VkIG1ldGhvZHMgb2ZmZXIgYSBtb3JlIHByZWNpc2UgbnVtZXJpY2FsIGFwcHJvYWNoIHRvIG91dGxpZXIgZGV0ZWN0aW9uIAogIGJhc2VkIG9uIHRoZSBkaXN0cmlidXRpb24gb2YgdmFsdWVzLCB3aGVyZWFzIGRlbmRyb2dyYW1zIHJlbHkgb24gdmlzdWFsIGludGVycHJldGF0aW9uLgoKCmMuIFVzZSBkdW1teSB2YXJpYWJsZXMgdG8gbWFrZSB0aGlzIGRhdGEgZnVsbHkgbnVtZXJpYyBhbmQgdGhlbiB1c2Ugay1tZWFucyB0byBjbHVzdGVyLiBDaG9vc2UgdGhlIGJlc3QgbnVtYmVyIG9mIGNsdXN0ZXJzLgoKYGBge3J9CiMgTG9hZCByZXF1aXJlZCBsaWJyYXJpZXMKbGlicmFyeShkcGx5cikKbGlicmFyeShjbHVzdGVyKQpsaWJyYXJ5KGZhY3RvZXh0cmEpCgojIExvYWQgYW5kIGNsZWFuIFN0YXJ3YXJzIGRhdGEKZGF0YSgic3RhcndhcnMiKQpzdGFyd2Fyc19jbGVhbiA8LSBzdGFyd2FycyAlPiUKICBzZWxlY3QoLW5hbWUsIC1maWxtcywgLXZlaGljbGVzLCAtc3RhcnNoaXBzKSAlPiUKICBkcm9wX25hKCkgJT4lCiAgbXV0YXRlKGFjcm9zcyh3aGVyZShpcy5jaGFyYWN0ZXIpLCBhcy5mYWN0b3IpKSAgIyBDb252ZXJ0IGNoYXJhY3RlciBjb2x1bW5zIHRvIGZhY3RvcnMKCiMgQ29udmVydCBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgdG8gZHVtbXkgdmFyaWFibGVzIHRvIG1ha2UgZGF0YSBmdWxseSBudW1lcmljCnN0YXJ3YXJzX251bWVyaWMgPC0gc3RhcndhcnNfY2xlYW4gJT4lCiAgbW9kZWwubWF0cml4KH4gLiAtIDEsIGRhdGEgPSAuKSAlPiUKICBhcy5kYXRhLmZyYW1lKCkKCiMgU3RlcCAxOiBEZXRlcm1pbmUgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzIHVzaW5nIHRoZSBFbGJvdyBhbmQgU2lsaG91ZXR0ZSBtZXRob2RzCnNldC5zZWVkKDEyMykgICMgRm9yIHJlcHJvZHVjaWJpbGl0eQoKIyBFbGJvdyBtZXRob2QKZnZpel9uYmNsdXN0KHN0YXJ3YXJzX251bWVyaWMsIGttZWFucywgbWV0aG9kID0gIndzcyIpICsKICBsYWJzKHRpdGxlID0gIkVsYm93IE1ldGhvZCBmb3IgT3B0aW1hbCBrIikKCiMgU2lsaG91ZXR0ZSBtZXRob2QKZnZpel9uYmNsdXN0KHN0YXJ3YXJzX251bWVyaWMsIGttZWFucywgbWV0aG9kID0gInNpbGhvdWV0dGUiKSArCiAgbGFicyh0aXRsZSA9ICJTaWxob3VldHRlIE1ldGhvZCBmb3IgT3B0aW1hbCBrIikKCiMgU3RlcCAyOiBBcHBseSBrLW1lYW5zIGNsdXN0ZXJpbmcgd2l0aCB0aGUgY2hvc2VuIG51bWJlciBvZiBjbHVzdGVycwojIEJhc2VkIG9uIHRoZSBFbGJvdyBvciBTaWxob3VldHRlIHBsb3QsIGNob29zZSB0aGUgb3B0aW1hbCBudW1iZXIgb2YgY2x1c3RlcnMgKGUuZy4sIGsgPSAzIGhlcmUgYXMgYW4gZXhhbXBsZSkKb3B0aW1hbF9rIDwtIDMKa21lYW5zX3Jlc3VsdCA8LSBrbWVhbnMoc3RhcndhcnNfbnVtZXJpYywgY2VudGVycyA9IG9wdGltYWxfaywgbnN0YXJ0ID0gMjUpCgojIERpc3BsYXkgY2x1c3RlciBhc3NpZ25tZW50IGFuZCBzdW1tYXJ5CnByaW50KGttZWFuc19yZXN1bHQkY2x1c3RlcikKdGFibGUoa21lYW5zX3Jlc3VsdCRjbHVzdGVyKQoKIyBWaXN1YWxpemUgdGhlIGstbWVhbnMgY2x1c3RlcnMgb24gYSBQQ0EtcmVkdWNlZCBwbG90IGZvciBlYXNpZXIgaW50ZXJwcmV0YXRpb24KZnZpel9jbHVzdGVyKGttZWFuc19yZXN1bHQsIGRhdGEgPSBzdGFyd2Fyc19udW1lcmljKSArCiAgbGFicyh0aXRsZSA9ICJLLW1lYW5zIENsdXN0ZXJpbmcgb2YgU3RhcndhcnMgRGF0YSIpCmBgYAoKUmVzdWx0cyBJbnRlcnByZXRhdGlvbjoKCkJhc2VkIG9uIHRoZSBrLW1lYW5zIGNsdXN0ZXJpbmcgYW5hbHlzaXM6CgoxLiAqKkVsYm93IE1ldGhvZCBhbmQgU2lsaG91ZXR0ZSBBbmFseXNpcyoqOiBCb3RoIG1ldGhvZHMgc3VnZ2VzdCB0aGF0IHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyBpcyBhcm91bmQgMy4KCiAgIC0gVGhlIEVsYm93IHBsb3Qgc2hvd3MgYSBzaWduaWZpY2FudCByZWR1Y3Rpb24gaW4gdG90YWwgd2l0aGluLWNsdXN0ZXIgc3VtIG9mIHNxdWFyZXMgdXAgdG8gayA9IDMsIGFmdGVyIHdoaWNoIHRoZSByZWR1Y3Rpb24gcmF0ZSBkaW1pbmlzaGVzLgogICAtIFRoZSBTaWxob3VldHRlIHBsb3QgYWxzbyBpbmRpY2F0ZXMgdGhhdCBrID0gMiBvciAzIGdpdmVzIHRoZSBoaWdoZXN0IGF2ZXJhZ2Ugc2lsaG91ZXR0ZSB3aWR0aCwgc3VnZ2VzdGluZyBiZXR0ZXItZGVmaW5lZCBjbHVzdGVycy4KCjIuICoqQ2x1c3RlciBBc3NpZ25tZW50cyoqOgoKICAgLSBDbHVzdGVyIDE6IENvbnRhaW5zIDEgb2JzZXJ2YXRpb24uCiAgIC0gQ2x1c3RlciAyOiBDb250YWlucyAyIG9ic2VydmF0aW9ucy4KICAgLSBDbHVzdGVyIDM6IENvbnRhaW5zIDI2IG9ic2VydmF0aW9ucy4KCjMuICoqVmlzdWFsIFJlcHJlc2VudGF0aW9uKio6IFRoZSBrLW1lYW5zIGNsdXN0ZXJpbmcgdmlzdWFsaXphdGlvbiBzaG93cyB0aGUgZGlzdHJpYnV0aW9uIG9mIGNsdXN0ZXJzIG9uIHRoZSBQQ0EtcmVkdWNlZCBkaW1lbnNpb25zLCB3aGVyZToKCiAgIC0gQ2x1c3RlciAxIChSZWQgQ2lyY2xlKSByZXByZXNlbnRzIGFuIG91dGxpZXIuCiAgIC0gQ2x1c3RlciAyIChHcmVlbiBUcmlhbmdsZSkgY2FwdHVyZXMgYSBzbWFsbCwgZGlzdGluY3Qgc3ViZ3JvdXAuCiAgIC0gQ2x1c3RlciAzIChCbHVlIFNxdWFyZSkgcmVwcmVzZW50cyB0aGUgbWFqb3JpdHkgb2YgZGF0YSBwb2ludHMsIHN1Z2dlc3RpbmcgYSBwcmltYXJ5IGdyb3VwaW5nIHdpdGhpbiB0aGUgZGF0YS4KCkluIHN1bW1hcnksIHRoZSBjbHVzdGVyaW5nIHJlc3VsdHMgc2hvdyBhIGxhcmdlIG1haW4gZ3JvdXAgKENsdXN0ZXIgMyksIHdpdGggdHdvIHNtYWxsZXIgY2x1c3RlcnMgKENsdXN0ZXJzIDEgYW5kIDIpIGNhcHR1cmluZyBwb3RlbnRpYWwgb3V0bGllcnMgb3Igc3ViZ3JvdXBzIHdpdGggZGlzdGluY3QgY2hhcmFjdGVyaXN0aWNzLgoKCmQuIENvbXBhcmUgdGhlIEhBQyBhbmQgay1tZWFucyBjbHVzdGVyaW5ncyB3aXRoIGEgY3Jvc3N0YWJ1bGF0aW9uLgoKYGBge3J9CiMgQXNzdW1pbmcgJ2hhY19jbHVzdGVycycgY29udGFpbnMgdGhlIEhBQyBjbHVzdGVyIGFzc2lnbm1lbnRzCiMgYW5kICdrbWVhbnNfY2x1c3RlcnMnIGNvbnRhaW5zIHRoZSBrLW1lYW5zIGNsdXN0ZXIgYXNzaWdubWVudHMKCiMgU3RlcCAxOiBQZXJmb3JtIEhBQyBjbHVzdGVyaW5nIGlmIG5vdCBhbHJlYWR5IGRvbmUKbGlicmFyeShjbHVzdGVyKQpnb3dlcl9kaXN0IDwtIGRhaXN5KHN0YXJ3YXJzX2NsZWFuLCBtZXRyaWMgPSAiZ293ZXIiKSAgIyBVc2luZyB0aGUgR293ZXIgZGlzdGFuY2UgZm9yIEhBQwpoYWNfcmVzdWx0IDwtIGhjbHVzdChnb3dlcl9kaXN0LCBtZXRob2QgPSAiYXZlcmFnZSIpCmhhY19jbHVzdGVycyA8LSBjdXRyZWUoaGFjX3Jlc3VsdCwgayA9IDMpICAjIENob29zZSBrID0gMyBiYXNlZCBvbiB0aGUgcHJldmlvdXMgYW5hbHlzaXMKCiMgU3RlcCAyOiBQZXJmb3JtIGstbWVhbnMgY2x1c3RlcmluZyBpZiBub3QgYWxyZWFkeSBkb25lCnNldC5zZWVkKDEyMykKa21lYW5zX3Jlc3VsdCA8LSBrbWVhbnMoc3RhcndhcnNfbnVtZXJpYywgY2VudGVycyA9IDMpICAjIEFzc3VtaW5nICdzdGFyd2Fyc19udW1lcmljJyBpcyB0aGUgZGF0YXNldCB3aXRoIGR1bW15IHZhcmlhYmxlcwprbWVhbnNfY2x1c3RlcnMgPC0ga21lYW5zX3Jlc3VsdCRjbHVzdGVyCgojIFN0ZXAgMzogQ3JlYXRlIGEgY3Jvc3N0YWJ1bGF0aW9uIGJldHdlZW4gSEFDIGFuZCBrLW1lYW5zIGNsdXN0ZXJzCmNyb3NzdGFiIDwtIHRhYmxlKGhhY19jbHVzdGVycywga21lYW5zX2NsdXN0ZXJzKQpwcmludChjcm9zc3RhYikKCiMgU3RlcCA0OiBJbnRlcnByZXRhdGlvbgpjYXQoIkludGVycHJldGF0aW9uIG9mIENyb3NzdGFidWxhdGlvbjpcbiIpCmNhdCgiVGhlIHRhYmxlIHNob3dzIGhvdyB0aGUgSEFDIGFuZCBrLW1lYW5zIGNsdXN0ZXIgYXNzaWdubWVudHMgYWxpZ24sIGluZGljYXRpbmcgdGhlIGNvbnNpc3RlbmN5IGJldHdlZW4gdGhlc2UgbWV0aG9kcy4iKQpgYGAKQW5zd2VyOgpJbnRlcnByZXRhdGlvbjogVGhlIHRhYmxlIHNob3dzIHRoZSBhbGlnbm1lbnQgYmV0d2VlbiBIQUMgYW5kIGstbWVhbnMgY2x1c3RlcnMsIHJldmVhbGluZyBzb21lIGxldmVsIG9mIGNvbnNpc3RlbmN5LiBGb3IgaW5zdGFuY2UsIEhBQyBjbHVzdGVyIDEgbGFyZ2VseSBvdmVybGFwcyB3aXRoIGstbWVhbnMgY2x1c3RlciAxLCB3aXRoIDE5IG9ic2VydmF0aW9ucyBhc3NpZ25lZCB0byBib3RoIGNsdXN0ZXJzLiBUaGlzIHN1Z2dlc3RzIHRoYXQgdGhlIHR3byBjbHVzdGVyaW5nIG1ldGhvZHMgaGF2ZSBpZGVudGlmaWVkIGEgc2ltaWxhciB1bmRlcmx5aW5nIHN0cnVjdHVyZSBmb3IgYSBzaWduaWZpY2FudCBwb3J0aW9uIG9mIHRoZSBkYXRhLiBIb3dldmVyLCB0aGVyZSBhcmUgbWlub3IgZGlzY3JlcGFuY2llcywgc3VjaCBhcyB0aGUgcHJlc2VuY2Ugb2Ygb2JzZXJ2YXRpb25zIGluIEhBQyBjbHVzdGVyIDIgdGhhdCBkbyBub3QgYWxpZ24gd2l0aCBrLW1lYW5zIGNsdXN0ZXJzLCB3aGljaCBjb3VsZCBpbmRpY2F0ZSBkaWZmZXJlbmNlcyBpbiBob3cgdGhlIHR3byBtZXRob2RzIGludGVycHJldCB0aGUgZGF0YSdzIHN0cnVjdHVyZS4gVGhpcyBjb21wYXJpc29uIGhpZ2hsaWdodHMgYm90aCB0aGUgYWdyZWVtZW50cyBhbmQgc3VidGxlIGRpZmZlcmVuY2VzIGJldHdlZW4gSEFDIGFuZCBrLW1lYW5zIGNsdXN0ZXJpbmcgZm9yIHRoaXMgZGF0YXNldC4KCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCg==